[Java] 백준 2606번 [바이러스] 자바

: ) YOUNG·2022년 4월 3일

DFS/BFS Java algorithm 백준 플로이드 워셜

알고리즘

목록 보기

79/422

백준 2606번
https://www.acmicpc.net/problem/2606

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

예제 출력 1

생각하기

DFS/BFS공부하려고 문제를 찾아서 풀려고 했는데,
풀이 방법을 생각하다보니 Floyd-Warshall 알고리즘으로도 충분히 풀 수 있겠다는 생각을 했다.

Floyd-Warshall은 원래 최소비용을 구하는 알고리즘이지만,
출발점으로부터 모든 경로를 탐색할 수 있다는 장점이 있기 때문에 1에서만 출발하는 조건에서 적한합 알고리즘이라고 판단했다.

그래서 먼저 Floyd-Warshall을 통해서 풀고
DFS, BFS를 이용해서 총 3가지 방법을 이용해서 풀어보기로 했다.

동작

arr[][] 의 2차원 배열을 먼저 생성한다.

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			arr[y][x] = 1;
			arr[x][y] = 1;
		}

여기서 Floyd-Warshall 알고리즘을 이용하기 위해
arr[i][j] 와 arr[j][i] 둘 다 1로 바꿔준다.

arr[][]가 완성되면,

Floyd-Warshall알고리즘의 floyd() 함수를 실행한다.

floyd() 함수는
k라는 다리를 통해 기존의 arr[i][j], arr[j][i] 로 이동할 수 있는 경로의 모든 곳에 1로 변환해준다.

즉, arr[i][k] 에서 arr[k][j] 둘 다 1일경우 이동할 수 있다고 판단하여 arr[i][j]를 1로 변경해준다.

이렇게 되면 arr[1]의 1로 된 값들이 1번 컴퓨터에서 이동할 수 있는 컴퓨터가 되므로
arr[1]의 1인 값들을 result++로 증가시켜

출력해주면 정답을 얻을 수 있게된다.

혹시 Floyd-Warshall알고리즘을 잘모르거나 한번 맛보고 싶으신 분들은
백준 11403 경로 찾기

위의 문제를 풀어보거나, 아래의 글을 읽어보길 바란다.
백준 11403 경로 찾기 풀이

문제를 풀고나서 아무래도 이 문제 자체가 DFS/BFS 문제다 보니 당연히 해당 알고리즘을 통해서도 풀어보는게 맞다는 생각을 해서
DFS, BFS를 이용해서 모두 풀어보았다.

DFS/BFS

DFS는 재귀를 사용했고, BFS는 Queue를 이용해서 탐색하는 반복은 똑같다

하지만 이 문제의 구조자체가 원래 양방향 그래프 개념을 가지고 있기때문에

(1,2)와 (2,1)은 같다는 것을 파악해야 한다.
그래서, 둘의 구조가 같기 때문에 arr[x][y] = arr[x][y] = 1의 구조가 된다.

이 배열을 완성하기 위해 arr은 2차원 배열로 만들어 주지만, 방문 여부를 표시하는 visit[]은 우리는 출발점인 1번 컴퓨터만 따지면 되기때문에 visit[]은 1차원 배열로 만들어준다.

이후 방문을 했는지와 1인지를 파악해서 조건에 맞춰 result를 증가시키면 정답을 얻을 수 있다.

풀어본 김에 또 비교를 안할 수 없지.
3가지 풀이를 비교해 보았다.

Floyd 알고리즘이 DFS/BFS보다는 아무래도 완전탐색 개념이다 보니 효율성이 좀 떨어질 수 밖에 없는 것 같다.
그래도 성공이라는 의미가 있는거니까 수확은 있다.

TMI

DFS/BFS 알고리즘 문제로 알고 들어왔지만, 다름 알고리즘을 응용해서 풀었다.
칭찬해 나 자신

코드

Floyd 알고리즘

import java.util.*;
import java.io.*;

public class Main {
	static int arr[][];

	static int N, M;
	static int result = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine()); // 컴퓨터의 수
		M = Integer.parseInt(br.readLine()); // 컴퓨터 쌍의 수

		arr	= new int[N+1][N+1];

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			arr[y][x] = 1;
			arr[x][y] = 1;
		}


		floyd();

		// 0과 자신인 1은 제외, 2부터 시작
		for(int i=2; i<N+1; i++) {
			if(arr[1][i] == 1) {				
				result++;
			}
		}

		System.out.println(result);

	} // End of main

	static void floyd() {

		for(int k=0; k<N+1; k++) {
			for(int i=0; i<N+1; i++) {
				for(int j=0; j<N+1; j++) {
					
					if(arr[i][k] == 1 && arr[k][j] == 1) {
						arr[i][j] = 1;
					}

				}
			}
		}

	} // End of floyd

} // End of class

BFS

import java.util.*;
import java.io.*;

public class Main {
	static Queue<Integer> que = new LinkedList<>();
	static int arr[][];
	static boolean visit[];

	static int N, M;
	static int result = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine()); // 컴퓨터의 수
		M = Integer.parseInt(br.readLine()); // 컴퓨터 쌍의 수

		visit = new boolean[N+1];
		arr	= new int[N+1][N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			arr[y][x] = 1;
			arr[x][y] = 1;
		}
		
		BFS();
		
		System.out.println(result);
	}// End of main
	
	public static void BFS() {

		que.offer(1);
		visit[1] = true;

		while( !que.isEmpty() ) {
			int node = que.poll();

			for(int i=1; i<N+1; i++) {
				// 1이 아니거나 visit[]이 true일 경우, 그냥 통과
				if(arr[node][i] != 1 || visit[i] == true) {
					continue;
				}

				que.offer(i);
				visit[i] = true;
				result++;
			}
		}

	} // End of BFS	
} // End of class

DFS

import java.util.*;
import java.io.*;

public class Main {
	static int arr[][];
	static boolean visit[];

	static int N, M;
	static int result = 0;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine()); // 컴퓨터의 수
		M = Integer.parseInt(br.readLine()); // 컴퓨터 쌍의 수

		visit = new boolean[N+1];
		arr	= new int[N+1][N+1];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			arr[y][x] = 1;
			arr[x][y] = 1;
		}

		DFS(1);

		System.out.println(result);
	} // End of main

	static void DFS(int node) {
		visit[node] = true;

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

			if(arr[node][i] == 1 && visit[i] == false) {
				DFS(i);
				result++;
			}
		}

	} // End of DFS
} // End of class