[백준] 1976 여행 가자 [java]

문제

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

풀이 방법

연결 그래프를 탐색하면서 해당 그래프 안에 도시가 모두 포함되는지 확인하면 되는 문제이다.
쉽다고 생각해서 그냥 풀었으나, 생각하지 못한 반례때문에
이렇게 되었다.
이 실수를 반복하지 않기 위해 글을 써본다.

실수

일단 이 문제를 보면 인덱스를 노드로 생각했을 때,

그래프를 이렇게 그릴 수 있다.
0번째 - 1번째
1번째 - 0번째 / 1번째 - 2번때
2번째 - 1번째
그런데 이렇게 하면 자기 자신을 탐색하는 방법이 없다.
만약,

3
1
0 0 0
0 0 0
0 0 0
2

이렇게 주어지면,

이렇게 이미 도시는 세 개 만들어진 상태이다. 그러면 1번째(도시 2)는 여행할 수 있다.
하지만, 배열 상에서는 그냥 모두 0이기 때문에 NO가 출력으로 나온다.
따라서, 자기 자신으로 가는 위치를 1로 초기화 해줘야 한다.
1 0 0
0 1 0
0 0 1
이렇게.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 여행 경로 가능한지 판별. 여러번 거쳐도 됨.
// 그래프 탐색 -> 여행 경로가 연결 그래프에 모두 포함됐는지
public class Main {

    public static void search(int[][] arr, boolean[] check, Set<Integer> travelCity,
                              int start){

        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while(!queue.isEmpty()){
            int curr = queue.poll();
            check[curr] = true;

            if(travelCity.contains(curr)) {
                travelCity.remove(curr);
            }

            for(int i = 0; i < arr[curr].length; i++){
                if(arr[curr][i] == 1 && !check[i]){
                    queue.add(i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bufferedReader.readLine());
        int city = Integer.parseInt(bufferedReader.readLine());
        int[][] arr = new int[size][size];
        for(int i = 0; i < size; i++){
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0; j < size; j++){
                arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                if(i == j) arr[i][j] = 1;		//자기 자신으로 가는 위치
            }
        }
        int[] travel = new int[city];
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < city; i++){
            travel[i] = Integer.parseInt(stringTokenizer.nextToken()) - 1;
        }

        boolean[] check = new boolean[size];

        boolean ans = false;
        for(int i = 0; i < size; i++){

            if(ans) break;

            for(int j = 0; j < size; j++){
                if(arr[i][j] == 1 && !check[j]){
                    Set<Integer> set = new HashSet<>();
                    for(int k = 0; k < travel.length; k++){
                        set.add(travel[k]);
                    }

                    search(arr, check, set, i);

                    if(set.size() == 0) {
                        ans = true;
                        break;
                    }
                }
            }
        }

        if(ans && city != 0) System.out.println("YES");
        else System.out.println("NO");
    }
}