[백준(Baekjoon)][자바(java)] 2606 : 바이러스 / 그래프와 순회

 

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

2606번: 바이러스

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()),
			m = Integer.parseInt(br.readLine()), u, v, i;
		List<List<Integer>> edge = new ArrayList<>();
		for (i = 0; i < n; ++i)
			edge.add(new ArrayList<>());
		StringTokenizer st;
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			edge.get(u).add(v);
			edge.get(v).add(u);
		}
		br.close();
		
		boolean visited[] = new boolean[n];
		visited[0] = true;
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);

		int cnt = -1;
		while (!queue.isEmpty()) {
			u = queue.remove();
			cnt++;
			for (int vv : edge.get(u)) {
				if (!visited[vv]) {
					visited[vv] = true;
					queue.add(vv);
				}
			}
		}

		System.out.println(cnt);
	}
}