[백준/2606][Java] 바이러스

문제

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

2606번: 바이러스

알고리즘

BFS, DFS

두 가지 방식으로 해결할 수 있다. BFS, DFS 두 가지의 풀이를 작성해 두었다.

arr을 전역변수로 선언하고 초기화하고 할당하는게 아직도 헷갈리지만, new이후 ArrayList<Integer>()를 하는 것이 객체를 생성하는 것이라고 생각하니 조금 더 이해가 잘 되는 것 같다.

우선 값을 입력받고 arr에 값을 저장한다.

그리고 bfs나 dfs를 모든 정점에서 진행할 필요 없이 1에서 단 한번만 진행하면 된다.

코드

package alone;

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

public class B2606_바이러스 {
	static int n, m, cnt;
	static ArrayList<Integer>[] arr;
	static boolean[] vis;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(br.readLine());

		arr = new ArrayList[n + 1];
		vis = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			arr[start].add(end);
			arr[end].add(start);
		}
		bfs(1);
		System.out.println(cnt);
	}

	private static void dfs(int i) {
		vis[i] = true;
		for(int v : arr[i]) {
			if(!vis[v]) {
				cnt++;
				dfs(v);
			}
		}
	}
	private static void bfs(int i) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(i);
		vis[i] = true;
		while(!q.isEmpty()) {
			int cur = q.poll();
			for(int v:arr[cur]) {
				if(!vis[v]) {
					cnt++;
					vis[v] = true;
					q.add(v);
				}
			}
		}
	}

}