Iyoungman Back-end Developer

BOJ 1976. 여행 가자

2020-04-29
Algorithm
     

Problem

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


Think

  • DFS/BFS로 풀어도 되지만, Union-Find로 풀었다.
  • 두 도시간의 경로가 연결되어있다는 의미는
  • 결국 두 도시의 최상위 부모가 같다는 의미이기 때문이다.

  • 직접 해결한 문제.


Solved Code

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Created by iyoungman on 2020-04-29.
 */

public class Main {

    private static int[] parents;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());//도시의 수
        int m = Integer.parseInt(br.readLine());//여행 계획의 수

        parents = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parents[i] = i;
        }

        //도시간 연결 입력
        for (int i = 1; i <= n; i++) {
            String[] lineSplits = br.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                int connect = Integer.parseInt(lineSplits[j - 1]);
                if (connect == 1) {
                    union(i, j);//(1)
                }
            }
        }

        //여행 계획 입력
        int[] travelPlans = new int[m];
        String[] lineSplits = br.readLine().split(" ");
        for (int i = 0; i < m; i++) {
            travelPlans[i] = Integer.parseInt(lineSplits[i]);
        }

        String result = "YES";
        for (int i = 1; i < m; i++) {
            int start = travelPlans[i - 1];
            int end = travelPlans[i];

            if (find(start) != find(end)) {//(2)
                result = "NO";
                break;
            }
        }

        //결과 출력
        System.out.println(result);
    }

    private static int find(int num) {
        if (parents[num] == num) {
            return num;
        } else {
            parents[num] = find(parents[num]);
            return parents[num];
        }
    }

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

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


Solved Process

1) 두 도시가 연결되어있다면 Union연산을 수행한다.

Union(x,y)는 x와 y가 포함되어 있는 집합을 합치는 연산이다.

부모를 합칠때는 일반적으로 더 작은쪽으로 합친다.


2) Find연산을 통해 여행경로가 유효한지 검증한다.

Find(x)는 x의 최상위 부모를 찾는 연산이다.

따라서 find(x) == find(y)라면 x,y는 같은 집합에 속했다고 할 수 있다.

Comments

Content