[백준 1976] 여행 가자 (JAVA)

백준 1976번 문제 - 여행 가자 

1976번: 여행 가자

---

문제 분석

 

• N(전체 도시 개수)하고 M(가고 싶은 도시 개수)을 입력받고,
• N(1 ≤ i ≤ N)번 N(1 ≤ j ≤ N)개씩 수가 주어진다.
  이 수는 i번 나라와 j번 나라의 연결 정보 입력 정보로 1이면 i와 j 나라가 연결되있음을 의미
• 가고 싶은 도시 M개를 입력 받는다.
• 가고 싶은 도시들이 다 연결되어 있어 모두 갈 수 있을 경우 YES, 아닐 경우 NO 출력

---

해결 키 포인트

 

• 유니온 파인드(union-find) 개념 사용
• i 나라와 j 나라가 연결 정보가 1일때, 무조건적으로 union(i, j)를 하면 안된다.
  WHY? 중복이 존재하기 때문 ➡️ 이미 처리한 나라인지 확인 후 확인 안할 경우 union(i, j) 실행
  • 이미 처리한 나라인지 : i 나라와 j 나라가 동일한 집합이면 이미 처리한 나라
  • find(a) != find(b) 여야지 union(i, j) 실행
    

---

유니온 파인트 (union-find)

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

 

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A∪B를 말한다.
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a, b가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. 

 

Union 연산 알고리즘

• 1차원 배열을 이용해서, i번째 값은 i로 변수 초기화한다. ( 대표 노드는 본인 )
• union(a, b) 연산은 a와 b의 대표 노드를 알아내 'b 대표 노드'의 value( list['b 대표 노드'] )을 'a 대표 노드'로 변경한다.
  • index == list[index] : 해당 index가 집합의 대표 노드
    index !=  list[index] : 대표 노드를 알아내야 함 ( 배열의 list[index]와 list[list[index]] 비교 )
  • list['b 대표 노드'] = 'a 대표 노드' 로 b 집합을 a 집합에 포함시킨다.

 

Find 연산 알고리즘

• 대상 노드 배열에 index 값과 value 값이 동일한지 확인
• 동일하지 않으면 value 값이 가리키는 index 위치로 이동
• 이동 위치의 index 값과 value 값이 같을 때까지 앞 방법들을 반복 (재귀함수로)
• 대표 노드에 도달하면 재귀함수를 빠져나오면서 거치는 모든 노드 값을 대표 노드 값으로 변경

---

코드

 

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

public class Main {
    public static int [] collection;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N,M 입력
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        // N개의 집합 생성
        collection = new int [N+1];
        for(int i=0;i<=N;i++) {
            collection[i] = i;
        }

        // N개의 도시 연결 정보
        for(int i=1;i<=N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1;j<=N;j++) {
                // isContain: 1이면 i번과 j번이 연결 O, 0이면 연결 X
                int isContain = Integer.parseInt(st.nextToken());
                if (isContain == 1 && find(i) != find(j)) {
                    union(i, j);
                }
            }
        }

        // M개의 가고 싶은 나라 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        boolean isTripPossible = true;
        int country = Integer.parseInt(st.nextToken());
        for(int i=0;i<M-1;i++) {
            int gotoCountry = Integer.parseInt(st.nextToken());
            if(find(country) != find(gotoCountry)) {
                isTripPossible = false;
                break;
            }
        }

        // 만약 isTripPossible가 true면 모두 여행 가능, 아니면 불가능
        if(isTripPossible)
            bw.write("YES");
        else
            bw.write("NO");
        bw.flush();
        bw.close();
    }

    public static void union(int a, int b) {
        int firstA = a, firstB = b;

        // a가 집합 대표가 아닐 경우 (a와 collection[a]가 동일 하지 않을 경우)
        if(a != collection[a])
            firstA = find(a); //  a 집합 대표 찾기 ( find(a) )


        // b가 집합 대표가 아닐 경우 (b와 collection[b]가 동일 하지 않을 경우)
        if(b != collection[b])
            firstB = find(b); //  b 집합 대표 찾기 ( find(b) )

        // b 집합의 대표를 a 집합의 대표로
        collection[firstB] = firstA;
    }

    public static int find(int a) {
        // a가 집합 대표일 경우 (a와 collection[a]가 동일 할 경우)
        if (a == collection[a])
            return a;

        //  a가 집합 대표가 아닐 경우
        collection[a] = find(collection[a]);
        return collection[a];
    }
}