Algorithms/백준

[BOJ] 백준 2606. 바이러스

devran 2023. 9. 3. 15:26
반응형

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번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

풀이

내가 정말 비선호하는,, 탐색문제, 익숙해져야겠지.

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

예시를 보면 1-2-3, 1-5-2(중복) 1-5-6 중복제외하면 총 4번 바이러스에 걸린다는 것을 알 수 있다.

나는 dfs로 풀어보기로 했다. 찾아보니 bfs가 속도는 더 느려도, 노드의 갯수가 많아진다면 안정성 측면에선 더 좋다고 한다. 두가지 다 할 줄 알아야 필요할 때 사용하기 좋을 듯.

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

public class Main {
	static int com[][] ;
	static boolean visited[];
	static int count = 0;
	static int N;
	static int M;
	
	public static void main(String[] args) throws IOException {
		  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		  StringTokenizer st;
		  N = Integer.parseInt(br.readLine()); // 컴퓨터 수 
	      M = Integer.parseInt(br.readLine()); // 네트워크 수 
	      
	      com = new int[N+1][N+1];
	      visited = new boolean[N+1];

	      for(int i =0; i <M; i++) { // 네트워크 수만큼 
	    	 st = new StringTokenizer(br.readLine());
	    	 int c1  = Integer.parseInt(st.nextToken());
	    	 int c2 = Integer.parseInt(st.nextToken());
	    	 com[c1][c2] = 1;
			 com[c2][c1] = 1; // 인접 행렬 만들어 주기 
	     }
	      DFS(1);
	      System.out.println(count);
	}
	public static void DFS(int start) { 
		
		visited[start] = true; //방문시 true 
		for(int i = 0 ; i <= N ; i++) {
			if(com[start][i] == 1 && visited[i]==false) { // 방문하지 않았을 경우 
				DFS(i); // 다시 순회 
				count++;
		}
		}
	}
}

탐색의 경우 집중공부를 좀 해야겠다.. 할때마다 새롭군

반응형