[백준 11562] 백양로 브레이크

++22.11.07 갱신.. 인간은 같은 실수를 반복.... 슬픔.. 

https://www.acmicpc.net/problem/11562

11562번: 백양로 브레이크

#include <cstdio>
#include <queue>
#include <cstring>
int N, M;
int K;
int Adj[250 + 2][250 + 2];

struct _st
{
	int node;
	int change;
};
std::queue<_st> Q;
int visited[250 + 2][250 + 2];	// s -> e로 가는 최소의 cost


void input()
{
	scanf("%d %d", &N, &M);
	for (int m = 0; m < M; m++) {
		int u = 0, v = 0, b = 0;
		scanf("%d %d %d", &u, &v, &b);
		if (b == 0) Adj[u][v] = 1;	// 단방향
		else if (b == 1) {			// 양방향
			Adj[u][v] = 1;
			Adj[v][u] = 1;
		}
	}

	// 자신 -> 자신 길이 무조건 있음 
	for (int i = 1; i <= N; i++) {
		Adj[i][i] = 1;
	}
}

void BFS(int start)
{
	// init
	Q = {};
	for (int j = 1; j <= N; j++) {
		visited[start][j] = 0x7fffffff;
	}

	Q.push({start, 0});
	visited[start][start] = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int next = 1; next <= N; next++) {	// 여기서 끝점 다 계산 해줄것이므로.. 
			if (visited[start][next] <= data.change) continue;

			// 이미 연결됨 
			if (Adj[data.node][next] == 1) {
				Q.push({ next, data.change });
				visited[start][next] = data.change;
			}
			// 일방향인데 양방향으로 바꿈 
			else if (Adj[next][data.node] == 1 && Adj[data.node][next] == 0) {
				if (visited[start][next] <= data.change + 1) continue;
				Q.push({ next, data.change + 1 });
				visited[start][next] = data.change + 1;
			}
			else continue;
		}
	}
}


void get_change()
{
	for (int i = 1; i <= N; i++) {	// 여기서  BFS N*N번 안돌려도 된다. 
		BFS(i);
	}
}

void output()
{
	scanf("%d", &K);
	for (int k = 0; k < K; k++) {
		int s = 0, e = 0;
		scanf("%d %d", &s, &e);
		printf("%d\n", visited[s][e]);
	}
}


int main()
{
	input();
	get_change();
	output();
	return 0;
}

 

 

 

 

---

이전 코드와 부연설명은 아래와 같다. 

#include <cstdio>
#include <queue>
#include <algorithm>
int N, M;
int K;

struct _st
{
	int n;	// 건물번호
	int t;	// 양방향으로 바꾼 개수
};

int Road[250 + 2][250 + 2];	// 길이 있는지 없는지 판단하기 위해 인접행렬 사용
int chk[250 + 2][250 + 2];

std::queue<_st> Q;

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int u = 0, v = 0, b = 0;
		scanf("%d %d %d", &u, &v, &b);
		if (b == 0)	Road[u][v] = 1;
		else {	// 양방향일때	
			Road[u][v] = 1;
			Road[v][u] = 1;
		}
	}
}



void BFS(int s)
{
	std::fill(&chk[s][0], &chk[s][0] + sizeof(chk[s]) / sizeof(int), 0x7fffffff);
	Q = {};
	Q.push({s, 0});
	chk[s][s] = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int i = 1; i <= N; i++) {
			int nn = i;
			int nt = 0;

			if (Road[data.n][nn]) nt = chk[s][data.n];	// data.n -> nn이면 길 변경 필요없음
			else if (Road[nn][data.n]) nt = chk[s][data.n] + 1;	// data.n -/-> nn 이지만 nn -> data.n이면 양방향으로 변경
			else continue;	// 연결되어있지 않으면 스루

			if (chk[s][nn] <= nt) continue;
			chk[s][nn] = nt;
			Q.push({ nn, nt });
		}
	} 
}



void search_all()
{
	for (int i = 1; i <= N; i++) {
		BFS(i);	// 모든 노드에 대하여 각 노드까지 도달하는데 필요한 길 변경 횟수 구함 
	}
}


void output()
{
	scanf("%d ", &K);
	for (int i = 0; i < K; i++) {
		int s = 0, e = 0;
		scanf("%d %d", &s, &e);
		printf("%d\n", chk[s][e]);
	}
}


int main()
{
	input();
	search_all();
	output();
	return 0;
}

ㅋ.. 고3때나 지금이나 신촌을 못가... 

날 힘들게 하는 Y대.... ^_ㅠ

 

 

이 문제는 모든 간선에 대하여 자기 자신 포함 다른 모든 간선으로 가기 위해 변경해야 하는 최소 길의 수를 구해야하는 문제이다. 따라서 1차원이 아니라, 2차원 체크 배열을 쓴다. 즉, chk[i][j]의 의미는 노드 i에서 노드 j로 가기 위해 변경해야 하는 최소 길의 수 이다. 

7% 타임아웃이 난 코드는 굳이 첨부하지는 않겠지만, 시작점 s와 목표점 e를 파라미터로 하여 BFS를 전체 한 번만 돌려주었다. 이렇게 하면 길이 양방향으로 갱신되었을 때를 고려할 수 없다. 따라서 모든 노드에 대하여 BFS를 돌려야 한다. 

 

 

// input( ) 함수

각 노드가 양방향으로 연결되어있는지, 단방향으로 연결되어 있는지를 빠르게 판단하기 위해 인접 행렬을 사용한다. 

노드 i와 노드 j가 단방향으로만 연결되어 있다면 Road[i][j] = 1 이고, 양방향으로 연결되어 있다면 Road[i][j] = 1, Road[j][i] = 1로 갱신해준다. 

 

 

// search_all( ) 함수

시작 노드 s를 정하기 위해 1 ~ N 범위에서 루프를 한번 돌려준다.  

 

 

// BFS( ) 함수

각 시작 노드 s에 대하여 1 ~ N노드까지 도달하는데 변경해야 하는 길의 수를 구하기 위한 함수이다. 

언제나 자기 자신 -> 자기 자신으로 갈 때는 길을 변경하지 않아도 되므로 chk[s][s] = 0이다.

 

이제 목적 노드 nn에 대하여 만약 방금 큐에서 pop된 노드 data.n과 목적노드 nn이 연결되어 있다면(Road[data.n][nn]) 길을 변경하지 않고도 도달할 수 있는것이므로 nt = chk[s][data.n](시작점 s에서 data.n까지 오는데 변경한 길의 횟수)를 저장한다. 

반면, 방금 큐에서 pop된 노드 data.n과 목적노드 nn이 단방향으로만 연결되어 있다면(Road[nn][data.n]) 길을 한 번 변경해야 하므로 nt = chk[s][data.n] + 1(시작점 s에서 data.n까지 오는데 변경한 길의 횟수 + data.n에서 nn까지 가기 위해 양방향으로 변경) 로 설정해준다.

아예 연결되지 않았다면 스루해준다.

 

만약 nt가 기존 체크배열에 저장되어 있던 최선의 결과보다 작을 경우에만 chk[s][nn]의 값을 위에서 저장한 nt로 갱신하고, 큐에 저장한다. 그렇지 않으면 스루해준다.