17352번 (유니온파인드)

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

17352번: 여러분의 다리가 되어 드리겠습니다!

 

이 문제는 트리의 구조를 탐색하여 그룹으로 나누는 유니온 파인드 알고리즘을 이용하거나 DFS를 활용하여 푸는 문제이다.

나는 그래서 유니온 파인드로 문제를 해결하였다.

 

동작방식은 부모노드를 저장 하는 리스트를 초기화하여서 루트 노드를 비교하여 서로 다른 그룹인지 같은 그룹인지 확인하는 방식이다.

여기서 중요한 것은 초기화 하는 방법인데 맨처음에 모든 노드에 대해서 자기 자신을 부모 노드로 설정하고, 입력으로 주어지는 값으로 부모 노드를 갱신하여 루트 노드를 수정하는 방법이다.

Graph g = new Graph(N);
for(int i=1; i<=N; i++){
    g.parent[i]=i; // 부모 노드를 자기자신으로 초기화
}

입력으로 주어진 노드간의 연결 간선은 아래의 코드로 처리한다.

for(int i=0; i<N-2; i++){
    StringTokenizer st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    g.union_root(u,v);
}

union_root메서드는 아래의 두 메서드를 이용한다.

4
1 2
1 3

입력이 위의 값으로 주어진다면, x=1, y=2 -> union_root(1,2) -> parent = [0,2,2,3,4]

x=1, y=3 -> union_root(1,3)-> parent = [0,2,3,3,4]

부모 노드를 정의한다.

find_root(1) -> [0, 3, 3, 3, 4]

find_root(2) -> [0, 3, 3, 3, 4]으로 정의되어서 1과 4의 root가 달라서 1 4를 출력한다.

public void union_root(int x, int y){
    x=find_root(x);
    y=find_root(y);
    if(x!=y){
        parent[x]=y;
    }
}

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

그래서 union_root는 루트 노드끼리의 연결을 해주는 로직이고, find_root는 탐색하는 노드의 부모 노드를 찾는 것이다.

즉, 노드 1의 root 노드는 3이고, 노드 4의 root 노드는 4이다.

 

find_root를 다시 정리해보면, 만약 1-2-3-4로 연결된 노드가 있을 때, find_root(4)를 돌리면 4의 부모는 3이고 3의 부모는 2이고 2의 부모는 1이고, 1의 부모는 1이니까 1을 반환하여 2의 부모를 1로 3의 부모를 1로 4의 부모를 1로 갱신하는 순서로 재귀한다.

4-3-2-1-2-3-4 의 순서로 돈다고 생각하면 된다.

 

정답 코드는 아래와 같다.

package backjoon.b17352;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class b17352 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Graph g = new Graph(N);
        for(int i=1; i<=N; i++){
            g.parent[i]=i;
        }
        for(int i=0; i<N-2; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.union_root(u,v);
        }
        for(int i=1; i<=N; i++){
            int a = g.find_root(1);
            int b = g.find_root(i);
            if(a!=b){
                System.out.println(1+" "+i);
                break;
            }
        }
    }
}
class Graph{
    int N;
    int[] parent;
    public Graph(int N){
        this.N = N;
        parent = new int[N+1];
    }
    public int find_root(int x){
        if(x==parent[x]) return x;
        return parent[x]=find_root(parent[x]);
    }
    public void union_root(int x, int y){
        x=find_root(x);
        y=find_root(y);
        if(x!=y){
            parent[x]=y;
        }
    }
}

최적화한 코드는 아래와 같다.

package backjoon.b17352;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b17352 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Graph g = new Graph(N);

        for(int i=1; i<=N; i++){
            g.parent[i]=i;
        }//자기 자신을 부모 노드로 초기화
        for(int i=0; i<N-2; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g.union_root(u,v);
        }//u 의 부모 노드를 v로 설정 설정
        for(int i=1; i<=N; i++){
            int a = g.find_root(1);
            int b = g.find_root(i);
            if(a!=b){
                System.out.println(1+" "+i);
                break;
            }
        }
    }
}
class Graph{
    int N;
    int[] parent;
    int[] depth;
    public Graph(int N){
        this.N = N;
        parent = new int[N+1];
        depth = new int[N+1];
    }
    public int find_root(int x){
        if(x==parent[x]) return x;
        return parent[x]=find_root(parent[x]);
    }
    public void union_root(int x, int y){
        x=find_root(x);
        y=find_root(y);
        if(x!=y){
//            parent[x]=y;
            if(depth[x]>=depth[y])parent[y]=x;
            else parent[x]=y;
            if(depth[x]==depth[y]){
                ++depth[y];
            }
        }
    }
}