백준 1976 - 여행가자 (JAVA)

백준 1976 - 여행가자 (JAVA)

 

 

 

1976번: 여행 가자 (acmicpc.net)

1976번: 여행 가자

 

 

유니언파인드로 풀려고 했는데, 이게 유니언파인드로 푼게 맞는지 모르겠네요.

유니언파인드에 대한 대략적인 개념만 읽고 푼 코드라서..

이렇게 푸는 사람도 있구나~ 정도로 참고만 해주시면 좋을 것 같습니다. 

 

 

 

푼 방법은 아래와 같습니다. 

 

[코드를 짠 대략적인 흐름]

  - map 2차원 배열에 0과 1로 제공되는 연결정보를 그대로 저장해준다.

  - map배열에서 1일 경우에는 서로 여행갈 수 있는 노선이 있다는 뜻이며(78행),

    info배열 안의 값을 비교했을 때 더 작은 값으로 업데이트 해준다. (81행~85행)

  - 최종적으로 여행지가 연결이 되어있는지에 대한 부분은 마지막에 제공되는 여행계획 순서 부분을 배열로 받은 뒤에 

    출발지와 목적지로 나누고, 출발지와 목적지에 대한 info값이 동일하다면 여행갈 수 있는 것이라고 판단하였습니다. (61행 ~ 70행)

  - find 함수를 두번 돌려주었는데, 이유는 아래의 참고반례 사례 때문입니다. 

  - 예를들어 총 5개의 여행지가 존재하고, 1-4 / 2-3 / 3-4 가 연결되어있다고 가정했을 때, 1-2-3의 순서대로 여행을 한다고 하면 YES가 나오는것이 맞습니다. (모든 여행지가 연결이 되어 있으므로)
하지만 코드를 잘못짰다면 NO가 출력될 것입니다. 잘못 출력될 수 있는 이유는 저의 코드 기준으로 3-4 연결부분에 대한 info배열 업데이트가 1-4 연결부분 업데이트보다 늦어지기 때문입니다. (코드 짜다 보시면 이해가 될거에요)

 

 

[참고반례]

아래 케이스를 넣었을 때 YES가 출력되어야 한다. 

 

5
3
0 0 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 1 0 0
0 0 0 0 0
1 2 3

 

정답 : YES

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Travel_Backjoon {
 
    static int N, M; // N = 도시의 수, M = 여행계획에 속한 도시들의 수
    static int [][] map; // 도시가 연결되어 있는지를 저장할 배열
    static int [] info; // 유니온파인드를 위한 배열
    static boolean [][] check;
 
 
    public static void main (String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken()); // 3 도시의갯수 : 3
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); // 3 여행할 도시의 수 : 3
 
        info = new int [N+1];
        check = new boolean[N+1][N+1];
        for (int i=1; i<=N; i++){
            info[i] = i; // 배열 초기화, 인덱스 번호에 그 수가 들어가도록 세팅
        }
 
        map = new int[N+1][N+1];
 
        for (int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine()); // 0 1 0
            for (int j=1; j<=N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for (int i=1; i<=N; i++){
            find(i);
        }
 
        check = new boolean[N+1][N+1];
        for (int i=1; i<=N; i++){
            find(i);
        }
 
        int [] travelplan = new int [M+1];
 
        st = new StringTokenizer(br.readLine()); // 1 2 3
 
        for (int i=1; i<=M; i++){
           travelplan[i] = Integer.parseInt(st.nextToken()); // travelplan[1] = 1
        }
 
        for (int i=1; i<=M-1; i++){
            int from = travelplan[i]; // 1 2
            int to = travelplan[i+1]; // 2 3
            if (info[from] != info[to]){
                System.out.println("NO");
                return;
            }
        }
 
        System.out.println("YES");
 
    }
 
 
    public static int find(int x){
 
        for (int i=1; i<=N; i++) {
            if (x!=i && map[x][i] == 1 && !check[x][i]) {   // map[2][1] == 1
                check[x][i] = true;
                check[i][x] = true;
                if (info[i] > info[x]){
                    info[i] = info[x];
                }else{
                    info[x] = info[i];
                }
            }
        }
        return info[x];
    }
 
}