[백준] 1976번 - 여행 가자 [Java]

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

 

[백준] 1976번 - 여행 가자 [Java]

[백준] 1976번 - 여행 가자 [Java]

---

1.  아이디어

 

여행을 가려는 도시가 모드 하나의 그래프 안에만 있으면 되므로 유니온 파인드 알고리즘으로 해결할 수 있다.

---

2. 문제풀이

 

union 연산으로 그래프를 구성한 후 Set을 활용해 여행가려는 각 도시의 그룹장을 저장했다.
Set의 크기가 1이면 모든 도시가 하나의 그래프 안에 있는 것이므로 여행을 갈 수 있다.

---

3. 코드

 

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

public class Main {

    private static int[] p;

    private static int[] make(int N) {
        int[] arr = new int[1 + N];
        for (int i = 1; i <= N; i++) {
            arr[i] = i;
        }
        return arr;
    }

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

    private static void union(int x, int y) {
        p[find(y)] = find(x);
    }

    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());

        p = make(N);

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                int bit = Integer.parseInt(st.nextToken());

                if (bit == 1) union(i, j);
            }
        }

        Set<Integer> set = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            set.add(find(Integer.parseInt(st.nextToken())));
        }

        if (set.size() == 1) System.out.println("YES");
        else System.out.println("NO");
    }
}

---

4. 후기