[백준] 1976번 : 여행 가자

1976번: 여행 가자

---

[Union-Find]

입력은 인접 행렬 형태로 주어지지만, 크루스칼 알고리즘을 사용할 때 처럼 모든 간선의 정보를 하나의 리스트에 담았고, 이 리스트를 가지고 유니온 파인드를 하여 서로 연결된 그래프라면 연결시켰다.

 

그리고 입력으로 주어진 m개의 여행 도시 배열의 각 원소의 부모가 첫 번째 원소의 부모와 다르다면 이 여행 순서는 이루어질 수 없으므로 "NO"를 출력한다.

# Code </>

public class Main {

    static class Edge{
        int h, tg;
        public Edge(int home, int target){
            h=home;
            tg=target;
        }
    }
    static List<Edge> list = new ArrayList<>();
    static int[] trip = new int[1001], parent = new int[201];

    static int getParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        return a == b? true : false;
    }
    static void unionParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

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

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

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

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                String s = st.nextToken();
                if(!s.equals("0"))
                    list.add(new Edge(i, j));
            }
        }

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=m; i++)
            trip[i] = Integer.parseInt(st.nextToken());

        for(Edge e : list){
            if(!findParent(e.h, e.tg))
                unionParent(e.h, e.tg);
        }

        boolean flag = true;

        for(int a=2; a<=m; a++)
            if(!findParent(trip[1], trip[a]))
                flag = false;

        System.out.println(flag?"YES":"NO");
    }
}