[BOJ 백준] 2606번 바이러스 - 자바

• 문제 : 2606번 바이러스
• 접근 유형 : bfs, 그래프

---

• 아래와 같은 조건을 파악 후 bfs를 사용하여 풀어야겠다고 생각했습니다. bfs를 통해 현재 노드와 인접한 노드를 큐에 넣고 방문할 수 있게 됩니다.

• 예시로서 아래와 같은 그림이 주어집니다. 이 그림을 보고, 노드와 간선으로 이루어진 그래프임을 알 수 있었으며, 연결 리스트 형태로 저장해야겠다고 생각했습니다. 특히, 1->2, 2->1로도 갈 수 있는 그래프 형태로서, 연결 리스트는 양방향으로 저장해야 함을 알 수 있었습니다.

 

---

- 구현 코드는 다음과 같습니다.

• 주의 사항 : 연결리스트 초기화가 필수입니다!!

public class Main {
	private static LinkedList<LinkedList<Integer>> list;
	private static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int vertex = Integer.parseInt(br.readLine());//컴퓨터의 수
		int edge = Integer.parseInt(br.readLine());//컴퓨터 쌍의 수
		
		list = new LinkedList<LinkedList<Integer>>();
		visited = new boolean[vertex+1];
		
		//list 초기화
		for (int i = 0; i <= vertex; i++) {
			list.add(new LinkedList<Integer>());
		}
		
		StringTokenizer st = null;
		for (int i = 0; i < edge; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			list.get(from).add(to);
			list.get(to).add(from);
		}
		
		bfs(vertex);
		
		//시작 노드 1번 제외 방문한 노드를 카운트하기 위해 인덱스 2부터 시작
		//방문한 노드는 연결된 노드이다.
		int count = 0;
		for (int i = 2; i < visited.length; i++) {
			if(visited[i]) count++;
		}
		
		System.out.println(count);
		
	}//end of main
	private static void bfs(int vertex) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);//1번 노드부터 시작
		
		while(!queue.isEmpty()) {
			int nowNode = queue.poll();
			visited[nowNode] = true;
			
			for (int i = 0; i < list.get(nowNode).size(); i++) {
				if(!visited[list.get(nowNode).get(i)]) {
					queue.add(list.get(nowNode).get(i));
				}
			}
		}
		
	}
	
}