[백준/JAVA] 1976번: 여행 가자

🔺 문제

1976번: 여행 가자

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] parent;
    
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();    // 도시 수
        int m = sc.nextInt();    // 여행 계획 도시 수
        
        // 도시 연결 데이터 저장
        int[][] city = new int[n + 1][n + 1];   // 인접 행렬
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++) {
                city[i][j] = sc.nextInt();
            }
        }
        
        // 여행 계획
        int[] route = new int[m + 1];
        for(int i = 1 ; i <= m ; i++) {
            route[i] = sc.nextInt();
        }
        
        // 대표 노드 자기 자신으로 초기화
        parent = new int[n + 1];
        for(int i = 1 ; i <= n ; i++) {
            parent[i] = i;
        }
        
        // 인접 행렬에서 도시가 연결되어 있으면 union
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n ; j++) {
                if(city[i][j] == 1) union(i,j);
            }
        }
        
        // 여행 계획 도시들이 1개의 대표 도시로 연결돼 있는지 확인
        int idx = find(route[1]);
        for(int i = 2 ; i < route.length ; i++) {
            if(idx != find(route[i])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
    
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b)
            parent[b] = a;
    }
    public static int find(int a) {
        if(a == parent[a]) return a;
        else               return parent[a] = find(parent[a]);
    }
}

✅ 해결 아이디어
✔ 유니온파인드

 

---

🔺 다른 풀이들

- 가장 깔끔.. (인접 행렬 사용 x & 입력 StringTokenizer 사용)

백준 1976번 여행 가자 (JAVA)

[BOJ] 백준 1976번 : 여행 가자 (JAVA)

 

 

- while(st.hasMoreTokens()) 사용

백준 1976 여행 가자 (Java,자바)

---

💬 느낀 점

 

 

 

1회독	2회독	3회독	4회독	5회독
V	6/22

 

 

(+ 6/22 2회독)

유니온 파인드는 이제 제법 마스터한 것 같습니다... 감사합니다..

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] parent;    // 부모 배열
    static int[][] map;     // 여행 정보 저장 배열 (인접 행렬)
    static int[] plan;      // 여행 계획 배열
    static boolean isPossible;  // 모두 연결되어있는지 여부 확인
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());    // 도시 수
        M = Integer.parseInt(br.readLine());    // 여행 계획에 속한 도시들 수
        
        // 부모 배열 초기화
        parent = new int[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            parent[i] = i;
        }
        
        // N개 줄 연결 정보 입력 받기
        map = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                if(map[i][j] == 1) {
                    union(i,j);
                }
            }
        }
        
        // 여행 계획 입력 받기
        plan = new int[M + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= M ; i++) {
            plan[i] = Integer.parseInt(st.nextToken());
        }
        
        // 여행 계획에서 find해서 모두 같은 집합일 때 (true) => YES
        isPossible = true;
        for(int i = 1 ; i < plan.length ; i++) {
            if(find(plan[i]) != find(plan[1])) {
                isPossible = false;
                break;
            }
        }
        System.out.println(isPossible ? "YES" : "NO");
    }
    
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    static int find(int a) {
        if(a == parent[a]) return a;
        return parent[a] = find(parent[a]);
    }
}
 

 

---

(참고)

✔ Do it 알고리즘 코딩 테스트 자바편

 

2023.04.28 - [코테/백준] - [백준/JAVA] 1717번: 집합의 표현

[백준/JAVA] 1717번: 집합의 표현