알고리즘 테크닉 - 좌표압축(grid compression)

1. 좌표압축이란

 

정점 번호가 1에서 $10^{9}$사이의 값으로 이루어져 있는 그래프가 하나 주어질때,

 

1번 정점에서 시작하여, 방문 가능한 서로 다른 노드의 수를 구하는 프로그램을 작성하세요.

 

 

일반적인 DFS 탐색으로는 1번 정점에서 N번 정점까지 번호가 매겨져 있어서,

 

큰 문제 없이 크기가 N인 visited 배열과 간선 정보를 나타내는 인접 리스트를 만들어 해결할 수 있습니다.

 

하지만 위와 같이 정점 번호가 1번에서 $10^{9}$사이로 주어진다면, visited 배열을 만드는 순간 메모리 초과로 일반적인 방법으로는 해결하기 어렵다.

 

그런데 조금만 생각해보면... 주어진 정점 번호를 오름차순으로 나열할때, 1,4,6,7,30,2000,$10^{9}$밖에 없으며..

 

이 정점들의 번호를 1번부터 순서대로 다시 매겨준다면...

 

1     -> 1
4     -> 2
6     -> 3
7     -> 4
30    -> 5
2000 -> 6
10^9  -> 7

 

이렇게 정점 번호를 변경한다면.. 마치 기존에 1~n번 사이의 번호로 주어진 문제처럼 해결할 수 있게 된다.

 

 

이를 좌표압축(grid compression)이라고 부른다.

 

위 과정은 다음 두 과정을 거쳐 진행할 수 있다.

 

1) 입력으로 들어온 모든 값을 treeset에 넣어준다.

 

2) 작은 숫자부터 순서대로 뽑아, 각 숫자에 번호를 매기고 그 결과를 hashmap에 넣어준다.

 

위의 예에서는 (1,1), (4,2), (6,3), (7,4), (30,5), (2000,5), (10^9,7) 형태로 hashmap에 들어가게 된다.

 

2. 구현 예시

 

파이썬부터 생각해보면.. 정점 번호를 오름차순으로 정렬하고 번호를 다시 매겨주면 되는데

 

edges = [(1,10**9), (1,2000), (1,4), (30,10**9), (6,7)]

nums = set()

#사용되는 모든 정점의 번호를 set에 넣어준다.

for v1,v2 in edges:
    
    nums.add(v1)
    nums.add(v2)

#sorted()를 이용해 오름차순 정렬된 리스트를 생성
sorted_nums = sorted(nums)


#grid compression
compression = dict()

i = 1

for num in sorted_nums:
    
    compression[num] = i
    
    print(num, "->", i)
    
    i += 1

#간선을, 압축한 정점 번호로 변경
for i in range(5):
    
    v1,v2 = edges[i]
    edges[i] = (compression[v1], compression[v2])

1 -> 1
4 -> 2
6 -> 3
7 -> 4
30 -> 5
2000 -> 6
1000000000 -> 7

 

 

자바로 구현하면 다음과 같다.

 

treeset이 뭔지 공부해야겠는데??

 

정렬된 set인것 같기는한데, 뭔가 정렬이 안되어있는데 정렬이 되어있는? 

 

균형잡힌 이진탐색트리라고 하는데 

 

import java.util.TreeSet;
import java.util.HashMap;

class Pair {
    int x,y;
    
    public Pair(int x, int y){
        
        this.x = x;
        this.y = y;
    
    }
};

public class Main {
    public static void main(String[] args) {
        
        Pair[] edges = new Pair[]{
            new Pair(1,(int)1e9),
            new Pair(1,2000),
            new Pair(1,4),
            new Pair(30,(int)1e9),
            new Pair(6,7),
        };
        
        TreeSet<Integer> nums = new TreeSet<>();
        
        //사용되는 모든 번호를 treeset에 넣어준다.
        
        for(int i = 0; i< 5; i++){
            nums.add(edges[i].x);
            nums.add(edges[i].y);
        }
        
        //treeset에서 정점을 작은 번호부터 뽑아
        //각 정점별로 1번부터 순서대로 매칭하여
        // 그 결과를 hashmap에 넣어준다.
        
        HashMap<Integer, Integer> mapper = new HashMap<>();
        int cnt = 1;
        
        //treeset을 순회하는 법으로 Integer num: nums로 간단하게
        for(Integer num: nums){
            mapper.put(num,cnt);
            //기존 정점번호마다 어떤 번호로
            //정해졌는지 출력
            System.out.println(num + " -> " + cnt);
            cnt++;
        }
        
        //주어진 간선을 이루는 정점 번호를
        //새로운 정점 번호로 변경
        for(int i = 0; i < 5; i++){
        edges[i] = new Pair(
        mapper.get(edges[i].x),
        mapper.get(edges[i].y)
        );
    }
}

1 -> 1
4 -> 2
6 -> 3
7 -> 4
30 -> 5
2000 -> 6
1000000000 -> 7

 

 

3. 연습문제

 

18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축

 

4. 풀이

 

압축하는 방법을 문제에서 제시해줬으니까, 그대로 구현하면 될것 같다

 

근데 풀어보니까 결국 위에서 구현한 좌표압축이랑 똑같은거임

 

from sys import stdin

n = int(stdin.readline())

grid = list(map(int,stdin.readline().split()))

sorted_grid = sorted(set(grid))

compression = {}

i = 0

for g in sorted_grid:
    
    compression[g] = i
    i += 1

for g in grid:
    
    print(compression[g], end = " ")