[백준] 2606번: 바이러스

 

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

2606번: 바이러스

 

---

[풀이 방법]

1. 키(정수) : 값(배열)을 갖는 HashMap 자료구조를 사용하여 컴퓨터의 연결을 저장 (그래프)

2. 방문한 노드는 더 이상 방문하지 않아도 되므로 방문기록을 표시 할 boolean 배열 visited를 선언

3. 연결되어 있는 컴퓨터부터 순차적으로 반복(bfs) 하기 위해 다음에 방문 할 노드를 담아 둘 Queue 자료구조 q 사용

 

여기서 부터 bfs 시작 ⤵

 

4. 첫 시작점 1을 방문기록 표시하고 큐에 추가

5. q가 비어질때까지 다음을 반복

    5-1. 컴퓨터를 꺼낸다

    5-2. 연결 된 컴퓨터들 중 방문하지 않은 컴퓨터들을 큐에 추가하고 바이러스에 감염된 컴퓨터 수(cnt)를 증가

           (만약 아무것도 연결되어 있지 않다면 큐에서 다음 컴퓨터를 꺼낸다)

 

6. 바이러스에 감염 된 컴퓨터 수 출력

 

[풀이 코드_Java]

*코드가 왜 밀리는지 모르겠다....😢

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
import java.util.HashMap;
import java.util.ArrayList;

public class Main {
	
	static int cnt = 0;
	static HashMap<Integer, ArrayList<Integer>> network = new HashMap<>();;
	static boolean[] visited;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
	    
		// 입력받은 값 각 변수에 저장 
		visited = new boolean[sc.nextInt() + 1];        // 방문기록 
	    int pairCnt = sc.nextInt();                     // 쌍의 개수            
		for (int i = 0; i < pairCnt; i++) {             // 네트워크 연결  
			int c1 = sc.nextInt(), c2 = sc.nextInt();
			
			if (network.get(c1) == null) {
				ArrayList<Integer> arr = new ArrayList<>();
				network.put(c1, arr);
			}
			network.get(c1).add(c2);
			
			if (network.get(c2) == null) {
				ArrayList<Integer> arr = new ArrayList<>();
				network.put(c2, arr);
			}
			network.get(c2).add(c1);
		}
		bfs();
		
		System.out.println(cnt);
	}
	
	public static int bfs() {
		
		Queue<Integer> q = new LinkedList<>();
		visited[1] = true;
		q.add(1);
		
		while(!q.isEmpty()) {
			int cpt = q.poll();
			if(network.get(cpt) == null) continue;
			
			for (Integer nextCpt: network.get(cpt)) {
				if (!visited[nextCpt]) {
					visited[nextCpt] = true;
					cnt++;
					q.add(nextCpt);
				}
			}
			
		}
		
		return cnt;
	}

}