[알고리즘] 백준 2606번 바이러스 :: 우유

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

2606번: 바이러스

---

간단한 DFS로 해결할수 있는 문제지만 ArrayList 와 Array 두가지 방법을 사용했을 때를 비교하고

두개 다 구현하는 방법을 연습하는 문제로 활용하였다.

---

Array로 구현한 DFS 

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

public class Main {

	static int N, M, V;
	static int map[][];
	static boolean visited[];
	static int cnt =0;

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		map = new int[N + 1][N + 1];
		visited = new boolean[N + 1];

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			map[y][x] = 1;
			map[x][y] = 1;
		}

//		DFS(1);
//
//		Arrays.fill(visited, false);
//		System.out.println();
		
		BFS(1);
		System.out.println(cnt);
	}

	static void DFS(int i) {
		visited[i] = true;
		System.out.print(i + " ");

		for (int j = 1; j < N; j++) {

			if (map[i][j] == 1 && visited[j] == false) {
				visited[j] = true;
				DFS(j);
			}
		}
	}

	static void BFS(int i) {
		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(i);
		visited[i] = true;

		while (!q.isEmpty()) {

			int temp = q.poll();
//			System.out.print(temp + " ");

			for (int j = 1; j <= N; j++) {

				if (map[temp][j] == 1 && visited[j] == false) {
					cnt ++;
					visited[j] = true;
					q.offer(j);
				}
			}
		}
	}
}

ArrayList 로 구현한 DFS 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static ArrayList<ArrayList<Integer>> al = new ArrayList<>();
	static int N, M;
	static boolean[] Visited;

	static int cnt =0;

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());

		Visited = new boolean[N + 1];

		Arrays.fill(Visited, false);
		for (int i = 0; i <= N; i++) {
			al.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			al.get(x).add(y);
			al.get(y).add(x);
		}

		DFS(1);
		
		System.out.println(cnt-1);
	}

	static void DFS(int V) {
		Visited[V] = true;

		cnt ++;
		for (int i = 0; i < al.get(V).size(); i++) {
			int temp = al.get(V).get(i);

			if (!Visited[temp]) {
				DFS(temp);
			}
		}
	}
}