😆😆

문제링크

백준 #1976. 여행 가자

풀이방법

백준 > #1717. 집합의 표현 문제랑 풀이방법이 98% 같은 문제입니다 ㅎㅎ

위 문제와 같이 집합합치기/같은집합여부 연산만으로 해결가능한 문제죠? 유니온파인드를 사용했습니다! 도시들 간의 연결 정보를 받고 "1"이면 두 도시를 merge하는 연산을 진행했습니다. 그리고 여행경로의 첫번째 도시의 루트를 저장해두고, 뒤따라오는 도시들의 루트를 find해 동일한 루트를 갖는지 확인했습니다! 쉬운문제네용

코드

import java.util.Scanner;

public class LetsGoTrip {
    static final int ROOT = -1;
    static int[] p;

    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] map = new int[n][n];
        p = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) map[i][j] = sc.nextInt();
            p[i] = ROOT;
        }

        for (int a = 0; a < n; a++) {
            for (int b = 0; b < a; b++) if (map[a][b] == 1) merge(a, b);
        }

        int result = 1;
        int commonRoot = find(sc.nextInt() - 1);
        for (int i = 1; i < m; i++) {
            if (find(sc.nextInt() - 1) != commonRoot) {
                result = 0;
                break;
            }
        }

        System.out.print((result == 1) ? "YES" : "NO");
    }

    private static int find(int id) {
        if (p[id] == ROOT) return id;
        else {
            p[id] = find(p[id]);
            return p[id];
        }
    }

    private static void merge(int idA, int idB) {
        int aRoot = find(idA);
        int bRoot = find(idB);

        if (aRoot != bRoot) p[bRoot] = idA;
    }
}

📚