[백준] 1976번 - 여행 가자

 

1976번: 여행 가자

 

 

 

1번부터 N번까지의 도시가 있을 때, 입력으로 i 번째 도시와 j 번째 도시의 연결 여부가 주어질 때 여행 계획의 모든 도시를 방문할 수 있는지 확인하는 문제이다. 따라서 도시가 정점이고 도시간의 연결 정보가 정점간의 간선인 그래프로 치환하여 접근할 수 있겠다. 추가로 도시간의 연결은 양방향성을 가지므로 무방향 그래프이고 여행 계획 순서대로 여행을 하는 동안 이미 방문한 도시를 중복해서 방문하는 것이 가능하다고 하였으므로 여행 계획에 있는 도시들이 하나의 연결 요소에 속하는지 판별하면 문제를 해결할 수 있다. 

 

그래프 내 정점들이 연결되어 있는지 확인하기 위해서는 DFS, BFS, Union Find 등을 사용할 수 있는데 이번 풀이에서는 유니온 파인드를 사용하였다.

 

유니온 파인드 관련 설명은 아래글 참고

[알고리즘] 유니온 파인드(Union Find)

 

 

 

 

 

전체 코드

import java.io.*;

public class Main {
	
	static int[] parent;
	
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        // 각 노드에 대한 부모 노드를 저장
        parent = new int[N+1];
        for (int i=1; i<=N; i++) parent[i] = i;
        
        String[] input = null;
        for (int i=1; i<=N; i++) {
            
            input = br.readLine().split(" ");
            
            for (int j=0; j<N; j++) {
                
                int check = Integer.parseInt(input[j]);
                
                // 두 도시가 연결된 상태라면 union 처리
                if (check == 1) 
                    union(i, j+1);
            }
        }
        
        input = br.readLine().split(" ");
        
        boolean flag = true;
        
        // 첫 번째 도시를 기준으로 여행 계획에 속한 도시들의 연결 여부를 확인한다. 
        int root = parent[Integer.parseInt(input[0])];
        for (int i=1; i<M; i++) {
            
            int city = Integer.parseInt(input[i]);
            
            // 연결되어 있지 않은 도시가 여행 계획에 포함되는 경우 NO 출력
            if (findParent(city) != root) {
                flag = false;
                break;
            } 
        }
        
        if (flag) System.out.println("YES");
        else System.out.println("NO");
        
        br.close();
    }
    
    static int findParent (int node) {
        if (parent[node] == node) return node;
        return parent[node] = findParent(parent[node]);
    }
    
    static void union (int a, int b) {
        int aParent = findParent(a);
        int bParent = findParent(b);
        
        parent[bParent] = aParent;
    }
}