[백준] 바이러스 (플로이드-와샬, DFS)

DFS로 풀었을때는 쉽게 풀었는데 플로이드-와샬로 풀었을때는 많이 애먹은 문제로, 이전에 경로 찾기 문제와 유사한 유형이다.

 

백준 2606번 바이러스

백준 2606번 입력 / 출력

 

입력 값은 아래와 같다.

 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

 

플로이드-와샬로 풀었을때 상당히 애먹었다. 이전 경로 찾기 문제에서도 출발지 -> 목적지가 직접 연결되지 않더라도 출발지 -> 경유지 -> 목적지가 가능하다면 출발지 -> 목적지가 가능하다는 내용이 있었는데, 이전 문제의 경우에는 모든 위치에 대하여 이동이 가능한지에 대해 물어보다 보니 플로이드-와샬로 쉽게 풀 수 있었다.

 

그런데 이 문제는 출발지가 1로 정해져 있어서 오히려 생각하는데 더 많은 시간이 들었다. 코드는 아래와 같다.

 

#include <stdio.h>
#define MAX 101

int Network[MAX][MAX];

int main(void) {
	int V = 0;
	int C = 0;
	int R = 0;
	
	scanf("%d", &V);
	scanf("%d", &C);
	
	for (int i = 0; i < C; i++) {
		int v1 = 0, v2 = 0;
		
		scanf("%d %d", &v1, &v2);
		
		// 양방향 그래프이므로 역방향도 1로 저장
		Network[v1][v2] = 1;
		Network[v2][v1] = 1;
	}
	
	//플로이드-와샬 시작
	for (int k = 1; k <= V; k++) {
		for (int s = 1; s <= V; s++) {
			for (int d = 1; d <= V; d++) {
				// 출발지 / 목적지가 같으면 패스
				if (s == d) {
					continue;
				}
				
				// 출발지 > 경유지 > 목적지 경로가 가능한지 확인
				if (Network[s][k] && Network[k][d]) {
					// 출발지 > 목적지 이동 가능
					Network[s][d] = 1;
					Network[d][s] = 1;
				}
				
				// 컴퓨터 1에서 출발했을때 도착 가능한지 확인
				if (Network[1][k] && Network[k][d]) {
					// 출발지 1 > 목적지 이동 체크
					Network[1][d] = 1;
					Network[d][1] = 1;
				}
			}
		}
	}
	
	// 컴퓨터 1을 제외한 나머지를 확인하기 때문에 2부터 시작
	for (int v = 2; v <= V; v++) {
		if (Network[1][v]) {
			R++;
		}
	}
	
	printf("%d\n", R);
	
	return 0;
}

 

모든 장소에 대해 연결되었는지 확인하는 것은 출발지 > 경유지 > 목적지가 가능한가만 따지면 되지만, 이 문제는 출발지가 1로 정해져 있으므로 출발지 1 > 경유지 > 목적지가 가능한지도 확인이 필요하다.

 

// 컴퓨터 1에서 출발했을때 도착 가능한지 확인
if (Network[1][k] && Network[k][d]) {
  // 출발지 1 > 목적지 이동 체크
  Network[1][d] = 1;
  Network[d][1] = 1;
}

 

출발지가 1일 때 목적지까지 가능한지 체크하고 인접 행렬에 표시한다. 여기서도 문제가 잘 풀리지 않아 삽질을 했는데, 2차원 배열을 하나 더 선언하고 입력된 좌표를 넣지 않았더니, 이전 연결정보가 다 사라져서 경로가 끊겨 제대로 체크하지 못하는 문제가 발생했다. 이전 경로 찾기 문제처럼 DFS 이후에 방문한 좌표를 체크하고, 방문 정점 데이터를 초기화하는 것처럼 하려 했는데 생각이 꼬였다 ;;

 

출발지가 지정돼있으므로 답을 구할때도 출발지를 1로 설정하고, 1을 제외하라고 했기 때문에 2부터 반복문을 시작한다.

 

for (int v = 2; v <= V; v++) {
  if (Network[1][v]) {
  	R++;
  }
}

 

DFS 혹은 BFS로는 이 문제를 매우 쉽게 풀 수 있다. 경로를 따라가면서 방문한 정점들을 모두 체크하고 탐색이 끝난 뒤에 방문한 정점의 카운트만 세면 된다. 이 문제는 플로이드-와샬 보다는 DFS / BFS가 방문한 정점을 다시 체크하지 않으므로 성능적으로도 더 좋다.

 

#include <stdio.h>
#define MAX 101

int Map[MAX][MAX];
int Virus = 0;
int Visited[MAX * MAX];

void DFS(int startV, int endV, int pareC) {
	// 방문 표시
	Visited[startV] = 1;
	
	// MAP 탐색 시작
	for (int v = 1; v <= endV; v++) {
		// 방문하지 않았고, 이동 가능한 정점일 경우
		if (Visited[v] == 0 && Map[startV][v] == 1) {
			Virus++;
			DFS(v, endV, pareC + 1);
		}
	}
}

int main(void) {
	int N = 0;
	int E = 0;
	
	scanf("%d", &N);
	scanf("%d", &E);
	
	for (int i = 0; i < E; i++) {
		int first = 0;
		int second = 0;
		
		scanf("%d %d", &first, &second);
		
		Map[first][second] = 1;
		Map[second][first] = 1;
	}
	
	DFS(1, N, 0);
	
	printf("%d\n", Virus);
	
	return 0;
}

 

시작점이 1이므로 애초에 끊겨있는 4, 7은 Map[startV][v] = 0 이므로 들어가지도 않는다. 이 쉬운 것도 이렇게 오래 걸리는데 어떡하냐 진짜 ...