백준 1976번 : 여행 가자 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

여행 가자 골드 4

 

📖 문제

 

서로소 집합 또는 BFS-DFS 알고리즘 둘중 하나로 풀 수 있는 문제다.

 

주어진 섬들을 여행 시작점을 출발로 탐색해서

여행 계획 섬들을 전부 방문했는지만 따지면된다. 

 

서로소 집합의 경우 

여행 계획 섬들의 부모가 모두 같으면 여행 가능하다.

 

---

🔅 문제 풀이 [BFS]

import java.io.*;
import java.util.*;

public class Main {
    static boolean[] visited;
    static boolean[][] graph;

    // 방문한 곳을 여행 계획에서 체크하면 된다.
    // 여행계획 섬을 방문하지 않았다면 이는 불가능한 것
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        // 그래프 초기화
        graph = new boolean[n + 1][n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= n; j++) {
                graph[i][j] = st.nextToken().equals("1");
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] searchList = new int[m];
        for (int i = 0; i < m; i++) {
            searchList[i] = Integer.parseInt(st.nextToken());
        }


        bfs(searchList[0]);
        for (int i = 0; i < m; i++) {
            if (!visited[searchList[i]]) { // 방문하지 않았다면 계획대로 갈 수 없는 섬
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }

    private static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int next = q.poll();

            for (int i = 1; i < graph.length; i++) {
                if (graph[next][i] && !visited[i]) {
                    visited[i] = true;
                    q.add(i);
                }
            }
        }
    }

}

 

🔅 문제 풀이 [서로소 집합]

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    static boolean[] visited;
    static boolean[][] graph;

    static int[] parent;
    // 방문한 곳을 여행 계획에서 체크하면 된다.
    // 여행계획 섬을 방문하지 않았다면 이는 불가능한 것
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        parent = IntStream.range(0, n + 1).toArray();
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= n; j++) {
                if(st.nextToken().equals("1")) {
                    if (find(i) != find(j)) {
                        union(i, j);
                    }
                }
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int sum = 0;
        for (int i = 0; i < m; i++) {
            int idx = Integer.parseInt(st.nextToken());
            sum += parent[idx];
        }
        
        // 여행 계획의 부모들을 전부 더하고 m으로 나눴을 때 나눠떨어지면 같은 부모를 가리키는 것으로 가능한 여행
        if (sum % m != 0) { 
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }

    }

    // 합지기
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);

        // 더 작은게 부모
        if (a > b) {
            parent[a] = b;
        }else {
            parent[b] = a;
        }
    }

	//부모 찾기
    private static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

}

 

❗ 오답노트 / 필요한 지식

1.