자바(백준) 1976 여행 가자

오답 노트 & 새로 알게 된 점

이 문제는 두 가지 풀이를 소개해보겠다.

 

첫 번째 풀이는 제가 처음 접근했던 풀이법이고,

두 번째는 힌트를 얻어 풀게된 "유니온 파인드"를 사용한 풀이법이다.

 

첫 번째 풀이

문제에서 서로 그래프가 연결되있느냐를 물어보는 것이었다.

따라서 모든 점에서 bfs를 사용하면서 서로 연결이 되어있는지 확인했다.

 

dist[A][B] 배열을 사용하여,

A가 출발 노드, B가 거쳐가는 노드라 생각해서

연결리스트를 사용하면서 출발점은 고정하고, 거쳐가는 노드들을 모두 저장했다.

 

하지만 반례가 존재한다.

문제에서는 갔던 곳을 또 방문할 수 있다. 

즉, 이 말은 여행 노드가 1 1 이렇게 나타날 수도 있다.
아마 문제를 푸시다가 80%에서 틀렸습니다 받으신 분들은 이 부분을 놓쳤을 것이다.

반례
2
2
0 0
0 0
1 1

따라서 input 메서드에서 A[i].add(i) 부분을 추가해주어 문제를 해결할 수 있었다.

 

두 번째 풀이

구글링을 하면 제일 많이 나온 풀이이다. 

유니온 파인드는 그래프에서 떨어져있는 점이 서로 연결되어 있는가 확인하는 자료구조이다.

 

따라서 주어진 그래프에서 1인 노드들을 서로 연결(union) 한 뒤,

여행 계획이 주어지는데, 이 때 서로 같은 부모인지 확인하면 된다.

 

같은 부모가 아닐 경우 이어져있지 않기 때문에 NO를 반환하면 된다.

 

---

코드(첫 번째 풀이)

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static boolean[][] dist;
    static int N, M;
    static int[] target;
    static ArrayList<Integer>[] A;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        //연결 확인하려고 각 노드에서 출발하여 bfs를 돌림
        for (int i = 1; i <= N; i++) bfs(i);
 
        int cnt = 0;
 
        for (int i = 1; i <= M - 1; i++) {
            if(dist[target[i]][target[i+1]]) {
                cnt++;
            }
        }
 
        if(cnt == M - 1) System.out.println("YES");
        else System.out.println("NO");
 
    }
 
    static void bfs(int start) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(start);
 
        while (!q.isEmpty()) {
            int cur = q.poll();
 
            for (int next : A[cur]) {
                if(dist[start][next]) continue;
 
                q.offer(next);
                dist[start][next] = true;
            }
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = atoi(br.readLine());
        M = atoi(br.readLine());
 
        target = new int[M + 1];
        A = new ArrayList[N + 1];
        dist = new boolean[N + 1][N + 1];
        for (int i = 0; i <= N; i++) A[i] = new ArrayList<>();
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int k = 1; k <= i; k++) st.nextToken();
            for (int j = i+1; j <= N; j++) {
                int num = atoi(st.nextToken());
                if(num == 1){
                    A[i].add(j);
                    A[j].add(i);
                }
            }
        }
        for (int i = 1; i <= N; i++) A[i].add(i);
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= M; i++) {
            target[i] = atoi(st.nextToken());
        }
    }
}

 

코드(두 번째 풀이)

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int[] parent, target;
    static int N, M;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        for (int i = 0; i < M - 1; i++) {
            if(find(target[i]) != find(target[i+1])){
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = atoi(br.readLine());
        M = atoi(br.readLine());
 
        parent = new int[N + 1];
        target = new int[M];
 
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int num = atoi(st.nextToken());
                if(num == 1) union(i,j);
            }
        }
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            target[i] = atoi(st.nextToken());
        }
    }
 
    static int find(int v) {
        if(parent[v] == v) return v;
 
        parent[v] = find(parent[v]);
        return parent[v];
    }
 
    static void union(int u, int v) {
        u = find(u);
        v = find(v);
 
        if(u == v) return;
 
        if(u > v){
            parent[u] = v;
        }
        else{
            parent[v] = u;
        }
    }
}