[Gold IV] 여행 가자 - 1976 (Java)

문제 요약

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 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라는 여행경로를 통해 목적을 달성할 수 있다.

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

---

문제 분석

• 도시 간의 연결 상태를 입력받아서, 직접적인 경로가 있는 도시들을 연결한다.
• 각 도시의 루트는 자기자신으로 초기화.
• 직접적인 경로가 있는 도시들을 union을 통해 연결
• 여행계획에 포함된 도시들이 같은 그룸에 속해있는지 find를 통해 찾기.

---

코드

package Week20;

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

public class BOJ_1976 {
    // 각 도시간의 연결 상태를 저장하는 배열
    static int[][] cityConnections;
    // 각 도시의 루트를 저장하는 배열
    static int[] cityRoots, travelPlan;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 도시의 수 N과 여행 계획에 포함된 도시의 수 M을 입력 받음
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        cityConnections = new int[N + 1][N + 1];
        travelPlan = new int[M + 1];
        cityRoots = new int[N + 1];
        StringTokenizer st;
        // 도시간의 연결 상태를 입력 받음
        for (int r = 1; r <= N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 1; c <= N; c++) {
                cityConnections[r][c] = Integer.parseInt(st.nextToken());
            }
            // 초기에는 각 도시의 루트는 자기 자신
            cityRoots[r] = r;
        }
        // 여행 계획에 포함된 도시들을 입력 받음
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            travelPlan[i] = Integer.parseInt(st.nextToken());
        }
        // 도시간 연결 상태에 따라 Union 연산 수행
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (cityConnections[r][c] == 1) {
                    union(r, c);
                }
            }
        }
        // 첫번째 여행 도시의 루트를 찾음
        int firstCityRoot = find(travelPlan[1]);
        // 모든 여행 도시가 첫번째 도시와 같은 루트(즉, 연결된)를 가지는지 확인
        for (int i = 2; i < travelPlan.length; i++) {
            if (firstCityRoot != find(travelPlan[i])) {
                bw.write("NO");
                bw.close();
                return;
            }
        }
        // 모든 도시가 연결되어 있으면 "YES"를 출력
        bw.write("YES");
        bw.close();
    }

    // Union 연산: 두 도시를 연결. 두 도시의 루트 중 하나를 다른 하나의 자식으로 만듦
    private static void union(int city1, int city2) {
        city1 = find(city1);
        city2 = find(city2);
        if (city1 != city2) {
            cityRoots[city2] = city1;
        }
    }

    // Find 연산: 주어진 도시의 루트를 찾음
    private static int find(int city) {
        if (city == cityRoots[city]) {
            // city의 루트가 자신이면, 그것은 대표 노드(루트 노드)이다.
            return city;
        } else {
            // city의 루트가 자신이 아니라면, city의 루트 노드를 찾기 위해 재귀적으로 find 함수를 호출한다.
            // 이 때, city의 부모 노드를 그 루트 노드로 바로 연결하는 경로 압축을 수행한다.
            cityRoots[city] = find(cityRoots[city]);
            return cityRoots[city];
        }
//        return city == cityRoots[city] ? city : (cityRoots[city] = find(cityRoots[city]));
    }
}

---