문제

여행 가자 - 골드4

문제 이해

• 유니온 파인드 알고리즘을 이용하여 이어진 도시를 표시한다.
• 여행 경로를 시작경로와 현재 경로가 이어져있는지 확인하고 그에 따라 결과를 출력한다.

코드

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

public class Baekjoon_1976 {
  static int N;
  static int M;
  static int[] parent;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    parent = new int[N + 1];
    for (int i = 0; i < N + 1; i++)
      parent[i] = i;
    st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());
    for (int i = 1; i <= N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 1; j <= N; j++) {
        int isConnect = Integer.parseInt(st.nextToken());
        if (isConnect == 1) {
          union(i, j);
        }
      }
    }

    st = new StringTokenizer(br.readLine());
    int current = Integer.parseInt(st.nextToken());
    for (int i = 1; i < M; i++) {
      int next = Integer.parseInt(st.nextToken());
      if (!isSameParent(current, next)) {
        System.out.println("NO");
        System.exit(0);
      }
    }
    System.out.println("YES");
  }

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

  public static void union(int x, int y) {
    x = find(x);
    y = find(y);

    if (x != y) {
      if (x < y)
        parent[y] = x;
      else
        parent[x] = y;
    }
  }

  public static boolean isSameParent(int x, int y) {
    x = find(x);
    y = find(y);

    return x == y;
  }

}

코드 설명

앞서 포스팅한 집합의 표현 문제에서 사용한 알고리즘을 그대로 사용한다.
다만 다른 점이 있다면 여행 경로가 오름차순이 아닐 경우를 대비해 union 메서드를 다음과 같이 바꾸었다.

public static void union(int x, int y) {
    x = find(x);
    y = find(y);

    if (x != y) {
      if (x < y)
        parent[y] = x;
      else
        parent[x] = y;
    }
  }

여행 경로를 따라 여행할 수 있는지 확인하기 위해 같은 부모를 가르키고 있으면 그래프가 이어진 것을 의미하기 때문에 시작점과 그때그때 방문할 여행지점이 같은 부모를 가지고 있는지 확인하여 방문할 수 있는지 여부를 확인하였다.