[JAVA] 백준 (골드4) 1976번 여행 가자

링크

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

---

문제 설명

정답률 36.926%
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

---

입력 예제

• 첫 줄에 도시의 수 N이 주어진다.
• N은 200이하이다.
• 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다.
• M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다.
• i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다.
• 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다.
• A와 B가 연결되었으면 B와 A도 연결되어 있다.
• 마지막 줄에는 여행 계획이 주어진다.
• 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.

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

---

출력 예제

• 첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

YES

---

풀이

도시의 연결 유무를 Union-Find 연산을 이용해 해결한다. 우선 도시의 연결 정보가 인접 행렬의 형태로 주어지기 때문에 인접 행렬을 탐색하면서 Union 연산을 수행한다.

//인접 행렬 생성
int[][] city = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
    st = new StringTokenizer(br.readLine());
    
    for (int j = 1; j <= N; j++) {
        city[i][j] = Integer.parseInt(st.nextToken());
    }
}
//인접 행렬 탐색
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        if (city[i][j] == 1) {
            union(i, j);
        }
    }
}

합집합을 구성한 다음 경로에 속한 도시들의 대표 노드가 동일한지 판단한다.

boolean flag = true;
for (int i = 0; i < path.length - 1; i++) {
    if (!check(path[i], path[i + 1])) {
        flag = false;
        break;
    }
}
System.out.println(flag ? "YES" : "NO");

코드

//백준
public class Main {

    static int[] parents;

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

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());  //도시의 수
        int M = Integer.parseInt(br.readLine());  //여행 계획에 속한 도시의 수
        parents = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parents[i] = i;
        }

        int[][] city = new int[N + 1][N + 1];  //인접 행렬
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //인접 행렬 탐색
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (city[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        int[] path = new int[M];  //경로 정보
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            path[i] = Integer.parseInt(st.nextToken());
        }

        boolean flag = true;
        for (int i = 0; i < path.length - 1; i++) {
            if (!check(path[i], path[i + 1])) {
                flag = false;
                break;
            }
        }

        System.out.println(flag ? "YES" : "NO");
    }

    static int find(int x) {
        if (parents[x] == x) return x;
        return parents[x] = find(parents[x]);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a < b) {
            parents[b] = a;
        } else {
            parents[a] = b;
        }
    }

    static boolean check(int a, int b) {
        a = find(a);
        b = find(b);

        return a == b;
    }
}