[UNION-FIND] - G4_1976_여행가자

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

🌿 - 문제 설명

📌- 풀이

플로이드 워셜로 전체 그래프에서 갈 수 있는 곳을 전부 map에 기록을 하고 시작 지점에서 각각 지점까지 전부 갈 수 있다면 YES, 한 곳이라도 못간다면 NO를 출력하는 방식으로 풀었다.

 

 

플로이드 워셜로만 풀었는데 다른 풀이들을 찾다보니 Union_Find로 문제를 푸는 방식들이 많아서 그것들을 참고해서 다시 풀어봤다.

 

유니온 파인드에 대한 설명은 여기 블로그에 자세하게 설명되어 있다.

https://rachel0115.tistory.com/entry/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find-Java

유니온 파인드 (Union Find) - Java

 

유니온 파인드는 일단 각 노드들을 비교해서 연결되어 있으면 가장 작은 값을 부모로 설정하도록 만들면 되는데 여기서는 경로를 입력받을 때 1이면 i와 j가 연결되어 있으므로 parent배열을 초기화 시켜 주면서 각각 노드들의 parent를 정의해주면 된다.

 

그렇게 일단 모든 노드들의 parent 배열을 완성한다.

그리고 여행계획 도시들의 parent가 시작지점이라면 모든 도시를 여행할 수 있기 때문에 YES를 출력하고 시작지점과 여행 계획 도시들의 parent가 다르다면 NO를 출력하면 된다.

 

 

🔥 - Java 전체 코드(플로이드)

package 그래프.G4_1976_여행가자;

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

public class Main {
        public static int N,M;
        public static int[][] map;

        public static String result="YES";

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());

        map = new int[N][N];

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

        st = new StringTokenizer(br.readLine());
        Queue<Integer> que = new LinkedList<>();

        while(st.hasMoreTokens()){
            que.add(Integer.parseInt(st.nextToken()));
        }

        int[] arr = new int[que.size()];


        for(int k =0;k<N;k++){
            for(int i=0;i<N;i++){
                for(int j =0;j<N;j++){
                    if(map[i][k] == 1 && map[k][j] == 1){
                        map[i][j] = 1;
                    }
                }
            }
        }

        int num = que.size();
        int count = 0;
        int start = 0;
        while(!que.isEmpty()){
            arr[count] = que.poll()-1;
            if(count ==0) start = arr[count];
            count++;
        }

        for(int i =1;i<num;i++){
                if(map[start][arr[i]] == 0){
                    result="NO";
                }


        }

        System.out.println(result);


    }

}

 

중간에 문제를 잘못읽어서 여행계획을 큐로 입력받는 곳이 있는데 이렇게 해도 문제가 풀리기도 하고, 실수를 이렇게 남겨 놓아서 나중에 다시 봤을 때 반성하기 위해서 남겨 놓았다.

 

 

 

🔥 - Java 전체 코드(유니온 파인드)

package 그래프.G4_1976_여행가자;

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

public class Main2 {
        public static int N,M;

        public static int[] parent;

        static String result = "YES";

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());

        parent = new int[N];

        for(int i = 0 ;i<N;i++){
            parent[i] = i;
        }

        for(int  i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j =0;j<N;j++){
               int number = Integer.parseInt(st.nextToken());
                if(number == 1){
                    union(i,j);
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int start = find(Integer.parseInt(st.nextToken())-1);
        for(int  i=1;i<M;i++){
            int num = Integer.parseInt(st.nextToken());
            if(start != find(num-1)){
                result = "NO";
                break;
            }
        }

        System.out.println(result);





    }

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

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

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

        if(x != y) {
            if(x < y){
                parent[y] = x;
            }else{
                parent[x] = y;
            }
        }
    }

}