Baekjoon[14868] - 문명

링크

불러오는 중입니다...

 

문제설명

• 한칸씩 퍼지면서 한 덩어리가 되는 순간을 체크

문제풀이

• 영역퍼트리기 (BFS)
• 인접영역 체크
• 인접영역 합치기 (Disjoint Set - Union)

문제코드

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*
경로압축 O
Union방식 weight
*/

public class Main {

    public static int[] parent;

    /** 음수면 root이면서 rank수 이므로 -1로 초기화 */
    public static void makeSet(int v) {
//        자기 자신을 가르킴
        parent[v] = -1;
    }

    /** 포함된 집합의 root를 찾는다. */
    public static int findSet(int v) {
//      root인 경우
        if (parent[v] < 0) {
            return v;
        }
//        경로압축 - find하는 과정에서 거치는 노드들을 모두 parent[v]를 향하도록 만들어준다.
        else {
            parent[v] = findSet(parent[v]);
        }
//        경로 압축이 끝난 후, 부모반환
        return parent[v];
    }

    /** 두 트리를 결합한다. */
    public static void union_normal(int v1, int v2) {
//        v1 <- v2 병합
//        root = parent
        int root1 = findSet(v1);
        int root2 = findSet(v2);

//      두 원소를 포함한 집합이 같은 집합인 경우
        if (root1 == root2) {
            return;
        }

//        v1 <- v2 병합
        parent[root2] = root1;
    }

    /** 두 트리를 결합한다. */
//    집합에 포함된 노드의 개수를 rank로 두고 union하는 경우
    public static void union_by_weight(int v1, int v2) {
//        root = parent
        int root1 = findSet(v1);
        int root2 = findSet(v2);
//        rank = depth
        int rank1 = parent[root1];
        int rank2 = parent[root2];

//      두 원소를 포함한 집합이 같은 집합인 경우
        if (root1 == root2) {
            return;
        }

//        rank : 둘다 음수임, rank가 깊은 녀석에게 병합
//        rank v1 이 더 깊음 : v1 <- v2 병합
//        같은 경우는 둘 중 아무나 병합해도 상관없음 : v1 <- v2 병합
        if (rank1 <= rank2) {
            parent[root1] += parent[root2];
            parent[root2] = root1;
        }
//        rank v2 이 더 깊음 : v2<-v1 병합
        else if(rank1 > rank2){
            parent[root2] += parent[root1];
            parent[root1] = root2;
        }
    }

    /** 두 트리를 결합한다. */
//    집합의 height(최대 노드 depth)를 rank로 두고 union하는 경우
    public static void union_by_height(int v1, int v2) {
//        root = parent
        int root1 = findSet(v1);
        int root2 = findSet(v2);
//        rank = depth
        int rank1 = parent[root1];
        int rank2 = parent[root2];

//      두 원소를 포함한 집합이 같은 집합인 경우
        if (root1 == root2) {
            return;
        }

//        rank : 둘다 음수임, rank가 깊은 녀석에게 병합
//        rank v1 이 더 깊음 : v1 < -v2 병합
        if (rank1 < rank2) {
//            parent[root1] 의 height는 그대로 유지
            parent[root2] = root1;
        }
//        rank v2 이 더 깊음 : v2<-v1 병합
        else if(rank1 > rank2){
//            parent[root2] 의 height는 그대로 유지
            parent[root1] = root2;
        }
//        같은 경우는 둘 중 아무나 병합해도 상관없음 : v1 <- v2 병합
//        대신 병합되는쪽의 rank가 하나 증가함.
        else if(rank1 == rank2) {
//            parent[root1] 의 height는 하나 증가
            parent[root1] -= 1;
            parent[root2] = root1;
        }
    }

    public static int getRank(int v) {
        return -parent[findSet(v)];
    }

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static void main(String[] args) throws FileNotFoundException {
        //System.setIn(new FileInputStream("res/baekjoon/14868.txt"));
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] map = new int[N][N];
        int K = sc.nextInt();
//        {x,y} = {c,r}
        int[][] rc = new int[K][2];
//        {r,c}
        for (int i = 0; i < K; i++) {
            rc[i][1] = sc.nextInt()-1;
            rc[i][0] = sc.nextInt()-1;
        }

//        {r,c,root}
        LinkedList<int[]> q = new LinkedList<int[]>();
//        init
        for (int i = 0; i < K; i++) {
            map[rc[i][0]][rc[i][1]]=i+1;
            q.add(new int[] {rc[i][0],rc[i][1],i+1});
        }

//        Union-Find Setting
        parent = new int[K+1];
        for (int i = 1; i <= K; i++) {
            makeSet(i);
        }
        int union_cnt=0;


//        BFS    
        int year=0;
        int nr;
        int nc;

//        시작 칸들에 대해서 UnionFind
        for (int[] now : q) {
            for (int d = 0; d < 4; d++) {
                nr = now[0] + dir[d][0];
                nc = now[1] + dir[d][1];
//                경계 안에서 개척한 칸의 인접 칸이 개척지(n)이고, 나와 다른 문명일 때
                if(nr>=0 && nr<N && nc>=0 && nc<N
                    && map[nr][nc]!=0 && map[nr][nc]!=now[2]) {
//                    이미 연결되어있지 않은 문명이라면
                    if(findSet(now[2])!=findSet(map[nr][nc])) {
//                        문명 연결
//                        union_normal(now[2], map[nr][nc]);
                        union_by_weight(now[2], map[nr][nc]);
//                      union_by_height(now[2], map[nr][nc]);
                        union_cnt++;
                    }
                }
            }
        }

        int[] nowrc;
        while(!q.isEmpty()) {
            if(union_cnt==K-1)break;
            for (int i = 0, qsize = q.size(); i < qsize; i++) {
                nowrc = q.poll();
                for (int d = 0; d < 4; d++) {
                    nr = nowrc[0] + dir[d][0];
                    nc = nowrc[1] + dir[d][1];
//                    경계 안에서 인접 칸이 미개척지(0)일 때 퍼트리기
                    if(nr>=0 && nr<N && nc>=0 && nc<N
                        && map[nr][nc]==0) {
                        map[nr][nc]=nowrc[2];
                        q.add(new int[] {nr,nc,nowrc[2]});
                    }
                }
            }
//            인접 영역 다퍼트렸으면
            year++;
//            퍼트린 영역들의 인접칸들에 대해서 UnionFind
            for (int[] now : q) {
                for (int d = 0; d < 4; d++) {
                    nr = now[0] + dir[d][0];
                    nc = now[1] + dir[d][1];
//                    경계 안에서 개척한 칸의 인접 칸이 개척지(n)이고, 나와 다른 문명일 때
                    if(nr>=0 && nr<N && nc>=0 && nc<N
                        && map[nr][nc]!=0 && map[nr][nc]!=now[2]) {
//                        이미 연결되어있지 않은 문명이라면
                        if(findSet(now[2])!=findSet(map[nr][nc])) {
//                            문명 연결
//                            union_normal(now[2], map[nr][nc]);
                            union_by_weight(now[2], map[nr][nc]);
//                          union_by_height(now[2], map[nr][nc]);
                            union_cnt++;
                        }
                    }
                }
            }
//            boolean unified = true;
//            int init = Parent(1);
//            for (int i = 2; i <= K; i++) {
//                if(init != Parent(i))
//            }
        }

        System.out.println(year);
    }
}

아쉬운 점

• 꼼꼼함 부족
  • 초기 상태에서도 union을 진행하여 끝이날 수도 있다.
• Union 효율적인 방식으로 구현하지 못했음
  • 경로압축
  • Rank기준 Union
  • 둘다 사용하지 않았음
• LinkedList를 get방식으로 호출하면 시간이 오래 걸린다.

잘한 점

• 영역 퍼트리기 -> Union 순서대로 구현 잘했음
• Union공부함

효율성

• Disjoint Set 에서 Find탐색의 효율성을 높이는 방법
  • Rank 기준 Union
  • 경로압축
  • 하나도 안 썼을 경우 시간초과가 난다.
• LinkedList = new LinkedList 기준으로 탐색했을 경우

경로압축	Union방식	메모리(kb)	시간(ms)
X	X	-	시간초과
X	Weight	340968	2116
X	Height	341428	2304
O	X	341028	2212
O	Weight	342592	2184
O	Height	343068	2160

• 결론: 비슷비슷한데 하나도 안쓰면 차이가 크다.

 

• List 탐색 방법

  • index를 이용해 LinkedList.get(i)를 호출하면 시간초과가 걸림
    • Queue, ArrayDeque의 경우는 get(i)를 쓸 수 없어서 foreach밖에 사용을 못함.
  • foreach(int[] a : LinkedList)를 이용하여 검사하면 통과함

• Rank(Weight기준)로 Union 했을 경우

사용 자료구조	탐색방법	메모리(kb	시간(ms)
LinkedList = new LinkedList	index -> get	-	시간초과
LinkedList = new LinkedList	foreach	342224	2204
Queue = new LinkedList	foreach	341636	2224
Queue = new ArrayDeque	foreach	323140	2016
ArrayDeque = new ArrayDeque	foreach	326744	1900

• 결론
  • index -> get호출하면 시간초과가 난다.
  • LinkedList < Queue < ArrayDeque 로 속도가 빠르다