[Java] 백준 1976번 : 여행 가자(BFS, 유니온 파인드 풀이)

문제소개

 

---

BFS 풀이

첫 번째 풀이로 BFS를 떠올렸다.

1 -> 2 -> 3 과 같은 경로를 거칠 수 있는지 판단해야하므로 하나의 경로를 나아갈 때 마다 BFS를 통해 도달할 수 있는지 없는지 검사한다.

경로의 수가 많다면 시간초과가 발생할 수 있지만, 주어진 조건으로는 200 * 200 * 1000, 즉 4천만정도여서 시도해봤다.

문제설명이 조금 부실해 여행 경로에 연속된 숫자가 나올 수 있다는 점을 늦게알았지만 해당 조건을 추가해주니 AC를 받았다.

public class Main {

    static int[][] graph;
    static boolean[] visited;
    static String result = "YES";
    static int[] schedule;
    static int N, M;

    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());
        graph = new int[N + 1][N + 1];
        schedule = new int[M];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int n = Integer.parseInt(st.nextToken());
                if (n == 1) {
                    graph[i][j] = 1;
                }
            }
        }

        String[] tmp = br.readLine().split(" ");
        for (int i = 0; i < M; i++) {
            schedule[i] = Integer.parseInt(tmp[i]);
        }

        for (int i = 0; i < M - 1; i++) {
            visited = new boolean[N + 1];
            boolean go = bfs(schedule[i], schedule[i + 1]);
            if(schedule[i] == schedule[i + 1]) continue;
            if (!go) {
                result = "NO";
                break;
            }
        }

        System.out.println(result);
    }

    static boolean bfs(int start, int end) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);

        while (!q.isEmpty()) {
            Integer poll = q.poll();
            visited[poll] = true;
            for (int i = 1; i < N + 1; i++) {
                if (graph[poll][i] == 1 && !visited[i]) {
                    q.add(i);
                    if(i == end) return true;
                }
            }
        }
        return false;
    }
}

 

---

유니온 파인드 풀이

BFS의 경우 입력 조건이 조금만 까다로워지면 시간초과가 발생할 수 있지만, 유니온 파인드를 활용해 분리 집합 관계를 미리 파악해놓는다면 대량의 여행 경로가 입력으로 들어와도 통과할 수 있다.

find()에서 경로 압축을 위해 지속적으로 자신의 부모 노드값을 갱신하도록 재귀함수를 구성했다.

public class Main {

    static int[][] graph;
    static int[] schedule, parent;
    static int N, M;

    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());
        graph = new int[N + 1][N + 1];
        schedule = new int[M];
        parent = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int n = Integer.parseInt(st.nextToken());
                if (n == 1) {
                    graph[i][j] = 1;
                }
            }
        }

        String[] tmp = br.readLine().split(" ");
        for (int i = 0; i < M; i++) {
            schedule[i] = Integer.parseInt(tmp[i]);
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        for (int i = 0; i < schedule.length - 1; i++) {
            if (find(schedule[i]) != find(schedule[i + 1])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    static int find(int x) {
        if(x == parent[x]) return x;

        return parent[x] = find(parent[x]);
    }

    static void union(int x, int y) {
        int a = find(x);
        int b = find(y);

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