문제

임의의 도시 N개가 있고, 이 도시들은 연결되있을수도 있고 아닐수도 있다. 도시들은 직접적으로 연결되어있지 않아도 건너 건너 갈 수도 있다. 이때 동혁이가 짠 여행경로가 주어졌을 때 여행이 가능한지 여부를 출력하면 된다.

풀이

union find로 해결했다.

사용한 자료구조

• parent 배열 : 해당 도시에서 연결된 도시들 중 가장 값이 작은 도시를 부모로 가정해서 배열에 넣어준다. 초기값은 각 도시값이다.
• route 배열 : 동혁이가 짠 여행 경로
• city 이차원 배열 : 입력으로 주어지는 도시들의 연결 여부

흐름

1. 이중 for 문을 순회하면서 도시를 연결한다.
2. connection()은 두 도시의 값을 입력받아서 그들의 부모 값을 구한다.
   • getParent() : 재귀 호출로 상위 부모를 찾는다.
   • 그리고 a와 b 두 값중에 작은 값을 가지고 있는 것을 부모 값으로 바꿔준다.
3. 연결이 다 끝난 후에는 check()로 여행 경로가 가능한지 여부를 확인한다.
   • 여행 경로의 첫 시작값의 부모와 다른 도시의 부모값을 비교하여 같으면 true를 리턴해준다.
4. 결과 출력

소스 코드

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

public class BOJ_1976 {
    static int[] parent;
    static int[][] city;
    static int[] route;

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

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        parent = new int[n + 1];
        route = new int[m];
        city = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            parent[i] = i;

            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            route[i] = Integer.parseInt(st.nextToken());
        }

        /* 도시 연결 */
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (city[i][j] == 1) {
                    connection(parent, i, j);
                }
            }
        }

        if (check(parent, route)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

    }

    static int getParent(int[] parent, int a) {
        if (parent[a] == a) {
            return parent[a];
        } else {
            return parent[a] = getParent(parent, parent[a]);
        }
    }

    static void connection(int[] parent, int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);

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

    static boolean check(int[] parent, int[] route) {
        for (int i = 0; i < route.length; i++) {
            if (parent[route[0]] != parent[route[i]]) {
                return false;
            }
        }
        return true;
    }
}

헤멘 부분..

탐색 시간을 줄이겠답시고 도시 연결 부분에서

/* 도시 연결 */
for (int i = 1; i <= n; i++) {
	for (int j = i+1; j <= n; j++) {
    	if (city[i][j] == 1) {
        	connection(parent, i, j);
		}
	}
}

대각선 윗 부분으로만 연결을 하려고 했다.
이렇게 했을 경우 1-2, 3-4가 연결되어 있는 상황에서 추가로 2-3을 연결 할 때 4의 부모값은 바뀌지 않게된다!
그래서 모든 값을 연결하면서 부모값을 update 해줄 수 있도록 변경했다