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

문제 설명

1. 첫번째 줄에 도시의 갯수가 주어진다.
2. 그 다음은 여행 계획에 속한 도시의 수가 주어진다.
3. 다음부터 그 줄의 도시가 어디랑 연결되었는지 주어진다.
4. 마지막에는 여행을 가는 계획이 주어진다.

풀이 과정

1. 유니온 파인드 문제이다. 모든 도시가 연결되어 있는지를 파악한다.
2. 주어지는 값들을 유니온해서(parent에 연결) 같은 루트에 있다고 맞춰준다.
3. 이후로는 마지막에 주어진 계획 도시들이 다 같은 루트에 있는지만 파악하면 된다.

 

코드

import java.util.*;

public class Main
{
  private static int[] parent;
  
  private static int find(int x) {
    if (x == parent[x]) {
      return x;
    }
    
    return parent[x] = find(parent[x]);
  }
  
  private static void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
      parent[rootY] = rootX;
    }
  }
  
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        parent = new int[n + 1];
        
        // 최초 초기화
        for(int i=0; i<n+1; i++) parent[i] = i;
        
        for(int i=1; i<n+1; i++) {
          String input = sc.nextLine();
          String spl[] = input.split(" ");
          
          for(int j=1; j<spl.length; j++) {
            int line = Integer.parseInt(spl[j-1]);
            if(line == 1) {
              union(i, j);    // 각 도시를 연결해준다. 1이면 연결됨
            }
          }
        }
        
        // 연결되는 도시를 찾기 위해 입력
        String input2 = sc.nextLine();
        String spl2[] = input2.split(" ");
        
        boolean check = true;
        // 모든 도시가 연결되었는지를 찾기 위해서는 서로 인접한 것이 다 같다면 모두가 연결된 것이다.
        for(int i=1; i<spl2.length; i++) {
          if(!check) break;
          if(find(Integer.parseInt(spl2[i-1])) != find(Integer.parseInt(spl2[i]))) check = false;
        }
        
        if(check) System.out.println("YES");
        else System.out.println("NO");
    }
}