백준 2606 바이러스

이번 문제는 DFS 를 자바로 해결하는 연습을 해보았다.

지금까지 dfs 를 전부 2차원 배열을 table 로 활용하는 방식으로 해왔는데, 이번 문제의 경우는 그냥 vector 에 담아주기만 하면 되었다.

결국 사용은 하지 않았지만 pair 클래스를 만들고, arraylist에 인자로 pair를 이용하기도 해보았다.

Vector가 있는것도 알게 되었다.

 

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

public class Main {

    private static int cnt = 0;
    static int [] vis = new int[102];
    static int [][] table;
    static private int n = 0;

    public static void main(String[] args) {

        int pair_num;
        Queue<Integer> q = new LinkedList<>();

        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        table = new int[n+1][n+1];
        pair_num = scanner.nextInt();

        for (int i = 0; i < pair_num; i++) {
            int tmp_x, tmp_y;
            tmp_x = scanner.nextInt();
            tmp_y = scanner.nextInt();

            table[tmp_x][tmp_y] = 1;
            table[tmp_y][tmp_x] = 1;
        }

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

    public static void dfs(int start) {
        vis[start] =1;
        cnt++;
        for (int i = 1; i <= n; i++) {
            if (table[start][i] == 1 && vis[i] != 1) {
                dfs(i);
            }
        }
    }
}

결국 상하좌우를 돌면서 탐색하지 않고, 컴퓨터의 개수만큼 전부 for문을 돌리면서 문제를 해결하였다.

 

자바로 코테문제를 푸는건 아직 어색하다! 다음엔 좀 더 잘 해봐야지