백준 2606 바이러스 (DFS,BFS) / JAVA

 

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

2606번: 바이러스

 

문제분석

예제 입력을 노드와 그래프로 나타내면 아래와 같다 

숙주인 1번 컴퓨터로부터 연결되있는 노드들은 모두 감염된다

따라서 1번 노드와 연결된 노드 갯수를 구하면된다

 

DFS와 BFS 두가지 방식으로 풀어보겠다.

 

1. DFS방식

 1) 인접리스트를 그래프로 구현

 2) DFS구현

  (1) 방문한 노드와 연결된 정점을 순서대로 바이러스감염여부를 확인 한다. ex) arr[1] : {2,5}

  (2) 미감염 노드일 경우 바로 해당 노드와 연결된 정점을 먼저 체크한다. ex) arr[2] : {1,3,5}

  

정점 1 : 감염 -> 시작점이므로 카운트x

1 정점과 연결된 2, 5 검사 => 정점 2 감염 -> 감염갯수 : 1

2 정점과 연결된 1, 3, 5 검사 => 정점 3 감염 -> 감염갯수 : 2

3 정점과 연결된 2 검사 => 이미 감염되있으므로 돌아가서 2 정점과 연결된 5 검사결과 정점 5 감염 -> 감염갯수 : 3

5 정점과 연결된 1, 2, 6 검사 => 정점 6 감염 -> 감염갯수 : 4

6 정점과 연결된 5 검사 => 이미 감염되있으므로 5 정점 검사결과 종료 / 2 검사로 복귀

                                    => 2 정점 검사 종료 / 1 검사로 복귀

                                    => 1 정점과 연결된 5 검사 결과 이미감염되있으므로 1 정점 검사 결과 종료

                                    => 모든검사 결과 종료

 

* 1번 컴퓨터는 카운팅에 들어가지 않는다 / 요구사항이 1번컴퓨터로부터 감염된 컴퓨터니깐

 

public class boj_2606_DFS {
	
	static ArrayList<Integer>[] arr;
	static int[] virus;
	static int result = 0;

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n+1];
		virus = new int[n+1];
		for(int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		// 그래프그리기
		for(int j = 0; j < m; j++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			arr[u].add(v);
			arr[v].add(u);
		}
		dfs(1);
		System.out.println(result);
	}
	
	public static void dfs(int start) {
		virus[start] = 1;
		for(int x : arr[start]) {
			if(virus[x] == 0) {
				result++;
				dfs(x);
			}
		}
		
	}
}

 

2. BFS방식

 1). 인접리스트로 그래프 구현

 2). BFS구현

  (1) 시작점 노드를 큐에 삽입 후 시작점 노드와 연결 된 정점을 차례대로 순회 ex) arr[1] : {2,5}

  (2) 정점을 순회하며 방문여부를 확인 후 방문하지 않았으면 바이러스 감염횟수를 카운팅 하고 시작점으로 큐에 삽입 ex) arr[2] : {1,3,5}

 

정점 1 : 감염 -> 시작점이므로 카운트x => 큐 삽입(Queue : {1})

1 정점과 연결된 2, 5 검사(Queue : {}) => 정점 2 감염 -> 감염갯수 1 -> 큐 삽입(Queue : {2})

                                                            => 정점 5 감염 -> 감염갯수 2 -> 큐 삽입(Queue : {2, 5})

2 정점과 연결된 1, 3, 5 검사(Queue : {5}) => 정점 3 감염 -> 감염갯수 3 -> 큐 삽입(Queue : {5, 3})

5 정점과 연결된 1, 2, 6 검사(Queue : {3}) => 정점 6 감염 -> 감염갯수 4 -> 큐 삽입(Queue : {3, 6})

3 정점과 연결된 2 검사(Queue : {6}) => 감염없음

6 정점과 연결된 5 검사(Queue : {}) => 감염없음

큐가 비었으므로 BFS종료

 

public class boj_2606_BFS {
	
	static ArrayList<Integer>[] arr;
	static int n, result = 0;

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[n+1];
		for(int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		// 그래프그리기
		for(int j = 0; j < m; j++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			arr[u].add(v);
			arr[v].add(u);
		}
		
		bfs(1);
		System.out.println(result);
	}
	
	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] virus = new boolean[n+1];
		virus[start] = true;
		queue.add(start);
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			for(int x : arr[now]) {
				if(virus[x] == false) {
					virus[x] = true;
					result++;
					queue.add(x);
				}
			}
		}
	}
}