[백준] 유니온 파인드와 여행가자

시간복잡도 생각해보기

유니온 연산: 도시 연결 정보에 대해 최대 N^2 번 수행한다. O(N^2)

• 유니온 연산 자체는 O(1) 라고 함…

파인드 연산: 여행 계획에 대해 M번 수행한다. O(M)

→ O(N^2 + M) → O(N)?

• N ≤ 200, M ≤ 1000 이었으므로 O(MN^2) 까지 가능했었으므로 상관 없을듯

아이디어

여행 경로에 주어진 도시들이 순서대로 이동 가능한지 확인해야됨

단순히 직접 연결 여부가 아니라 중간 도시를 경유해서라도 도달 가능한지까지 봐야됨

처음 풀이: bfs → 복잡해서 풀다가 생각하기를 포기함

접근: 유니온 파인드 → 도시들을 집합으로 묶어서 같은 그룹에 속해 있는지를 판단한다.

• ex) 1번 - 2번 연결 → 같은 그룹, 2번 - 3번 같은 그룹, 1-2-3 ⇒ 모두 같은 그룹

왜 유니온 파인드인가?

• 도시들이 서로 연결되어있는지의 여부만 중요하기 때문이다.
• 유니온 파인드는 연결 여부만 판단하는데에 최적화된 알고리즘이다.
• 직접 가는 길이 없어도 다른 도시를 경유해서 갈 수 있으면 OK이기 때문이다.
• 연결되어있으면 같은 그룹, 즉 root 노드를 같게 해주면 된다.
• 모두 같은 그룹, 집합으로 묶어주는 경우에는 탐색할 필요 없이 한 줄로 부모가(그룹이) 같은지만 비교하면 된다.
• 방향이 없는 그래프이므로 같은 그룹에 있는 도시끼리는 경로가 무조건 존재하며, 경로는 내가 신경 쓸 필요 X 굳이 연결리스트를 만들어서 저장하지 않아도 됨 → 유니온 파인드

풀이

1. 모든 도시는 처음에 자기 자신을 부모로 선정한다.

parents[x] = x;

2. 도시 연결 정보를 받고 처리한다.

유니온

    - 만약, i번째 줄 j번이 **1**이면: 이어져있다는 의미이므로,  i,j의 루트노드가 같지 않은지 **find**로 검사하고
    - **같지 않으면**: j의 루트노드를 i의 루트노드로 선정한다. (같은 그룹으로 묶음)
    - 같으면: 이미 같은 그룹으로 지정되었으므로 넘어간다.

파인드

재귀를 이용해서 x == parents[x] 이면 x 를 리턴하고,
아니면 parents[x] = find(parents[x]) 해서 경로를 압축함

 parent[1] = 2
parent[2] = 3
parent[3] = 4
parent[4] = 4 (루트) -> 최종 부모

find()를 하면서 탐색 과정에서 만난 모든 노드의 부모를 한 번에 루트 노드로 바꿔버린다. (시간 압축)

parent[1] = 4
parent[2] = 4
parent[3] = 4
parent[4] = 4 -> 다 4로 업뎃 (어차피 연결되어 있으므로)

3. 첫번째 여행 도시를 시작 지점으로 잡고, 그 후 여행 도시들을 입력받으며, find(start) ≠ find(next) 즉 부모 노드가 같지 않으면 이어져있지 않다는 의미이므로 NO를 출력하고 종료한다.

• 다 가능하면 YES 출력

의사코드

자기 자신을 부모로 초기화

parents = new int[N + 1];
  for (int i = 1; i <= N; i++) {
      parents[i] = i; //자기 자신을 부모로 초기화한다.
  }

입력 정보를 받고 1 인경우 union 수행

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

파인드(루트 노드 찾기)

private static int find(int x){
    if(x == parents[x]) return x;
    return parents[x] = find(parents[x]); //경로 압축
}

유니온

private static void union(int a, int b){
    int rootA = find(a);
    int rootB = find(b);
    if(rootA != rootB){
        parents[rootB] = rootA;
    }
}

여행 경로 검사

st = new StringTokenizer(st.nextToken());

int start = Integer.parseInt(st.nextToken());

boolean isPossible = true;

while(st.hasMoreToken()){
    int next = Integer.parseInt(st.nextToken());
    if(find(start)!=find(next)){ // 시작 노드와 같은 그룹이 아니면 안됨
        isPossible = false;
        break;
    }
}

---

 

유니온 파인드 자체는 템플릿이 똑같으므로 외우면서 이해하면 되고, 이 문제는 어떤 경로든 상관없으니 갈 수만 있으면 되기 때문에 경로를 연결 리스트(List<Integer> [] ) 로 저장할 필요가 없는 문제였다. 하지만 BFS로 경로 탐색하려고 했던게 문제였음. 앞으로 연결 여부만 봐야한다면 유니온 파인드를 고려해보자