BOJ 27115 - 통신소 (Python3)

오늘 내가 몸담은 동아리 모르고리즘에서 월례 대회가 열렸다. 골드 이하로 다양한 태그의 교육적이고 인기 없는 문제 셋을 구성한다는 쉽지 않은 과제였을 텐데 역시 운영진이 모두 엄청난 실력과 선구안을 지닌 사람들이라 그런지 이대로 대회에 나와도 크게 손색 없을 법한 셋이 탄생되었다. 실력 없는 물로켓인 내가 풀기에 딱 알맞은 셋이었다. 아쉽게 좌셋은 아니었지만.

이 문제는 태그 덮고 난이도 덮고 풀었을 때는 마지막에 시간이 모자라서 못 풀었고, 이후 풀이 설명하는 시간에 내 풀이를 말로 설명하고 해설자인 Serendipity__의 말에 힌트까지 얻어 집에서 완성해 냈다. 중간에 IndexError가 자꾸 났는데, 0부터 3000까지 키를 가지는 배열의 길이를 3001이 아니라 3000으로 저장하는 치명적인 머저리같은 실수 탓이었다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

대한민국 공군은 비행하는 전투기와 지상에서 원활하게 통신하기 위하여 여러 위치에 통신소를 설치하였다. 지금까지 \(K\)개의 통신소를 배치하였는데, 각 통신소는 \((y_i,x_i)\)의 위치에서 전파 세기가 \(p_i\)인 전파를 발생시켜 \(|y_i-y|+|x_i-x|\le p_i\)인 모든 정수 \(y, x\)에 대하여 \((y,x)\)에서 비행하는 전투기와 통신할 수 있다. 서로 다른 위치에서 발생한 전파가 서로 만나더라도 전파 세기는 변함없다.

지도의 세로 크기 \(N\)과 가로 크기 \(M\), 통신소 \(K\)개의 위치와 전파 세기가 주어졌을 때, 지도 안에서 비행하는 전투기가 적어도 하나의 통신소와 통신할 수 있는 정수 격자점 \((y,x)\)의 개수를 구하여라.

 

입력

첫 번째 줄에 지도의 세로 크기 \(N\)과 가로 크기 \(M\), 통신소의 개수 \(K\)가 공백으로 구분되어 정수로 주어진다. \((1\le N,M\le 3\,000\); \(1\le K\le 300\,000)\)

 

예제 입력)

6 7 4
2 6 2
3 3 1
6 1 3
5 6 2

 

출력

지도 안에서 전투기가 적어도 하나의 통신소와 서로 통신할 수 있는 정수 격자점의 개수를 출력한다.

 

예제 출력)

35

 

---

내 코드

from sys import stdin
input = stdin.readline
N,M,K = map(int,input().split())
dx,dy = [1,-1,0,0],[0,0,1,-1]
box = [[-1]*M for _ in range(N)]
def inbox(x,y):
    if x<0 or x>=N: return False
    if y<0 or y>=M: return False
    return True 
giji = [set() for _ in range(3001)]
for _ in range(K):
    x,y,p = map(int,input().split())
    giji[p].add((x-1,y-1))
while len(giji) > 0:
    array = list(giji.pop()); power = len(giji)
    if power > 0:
        while array:
            x,y = array.pop()
            box[x][y] = power
            for i in range(4):
                nx,ny = x+dx[i],y+dy[i]
                if inbox(nx,ny):
                    if box[nx][ny] < power-1:
                        box[nx][ny] = power-1
                        giji[power-1].add((nx,ny))
    else:
        while array:
            x,y = array.pop()
            box[x][y] = 0
ans = 0
for row in box: ans += sum(1 for i in row if i >= 0)
print(ans)

 

당장 이 문제를 마주하자마자 할 수 있는 생각은 BFS이다. 그러나 나이브한 BFS로는 각 칸에 전파가 여러 번 들어올 수 있어서 금방 시간초과를 받게 된다. 각 칸을 한 번, 많아야 두 번 탐색해 주는 방법으로 풀어야 시간초과를 회피할 수 있다.

공식 에디토리얼에서는 세기가 강한 전파를 먼저 퍼져나가게 하는 BFS를 생각했는데, 나는 조금 더 다르게 생각하여 BFS보다는 재귀에 가까운 코드를 만들어 냈다. 골자는, 공식 에디토리얼과 비슷하게 "이미 전파가 \(power\)만큼 흐르고 있는 구역에 \(power\)보다 약한 전파를 흘려보내는 것은 안 흘려보내는 것과 마찬가지다"라는 관찰 하나와 "전파의 유무만 중요하다면 점 \(p\)를 중심으로 하고 \(power\)의 세기를 가지는 통신소는 \(power-1\)만큼의 세기를 중심으로 하고 \(p\)의 상하좌우 네 점을 각기 중심으로 하는 통신소 넷과 동등하다"라는 것 하나이다.

 

각 통신소를 key를 전파의 세기로 가지는 배열에 집어넣어 두자. 그 다음 전파 세기가 0이 될 때까지 위 관찰대로, \(p\)를 중심으로 하고 \(power\)만큼의 전파 세기를 가지는 통신소를 \(power-1\)만큼의 전파 세기를 가지고 \(p+(\pm1,0)\)과 \(p+(0,\pm1)\)을 중심으로 하는 통신소 넷으로 쪼개 주자. 다만, 쪼개줄 때 이미 쪼개진 통신소가 세워질 장소에 \(power\) 혹은 그 이상의 전파가 흐르고 있다면 그 곳에 통신소를 세울 필요는 없다. 이미 흐르고 있는 전파에 묻히기 때문이다.

그러면 정확한 연산 횟수를 증명하기는 힘들지만, 매 칸마다 전파가 흐르는(=새로운 통신소가 세워지는) 것은 최대 한 번이므로 시간 제한에 아슬아슬하게 걸리는 선에서 정리를 할 수 있다. 이게 명확한 풀이가 되는지는 잘 모르겠다. 시간복잡도 증명을 하기 힘들어서... 하지만 그래도 통과했으니 된 게 아닐까 싶기도 하고.

만일 이 풀이의 시간복잡도를 증명한 사람이 있으면 어떤 경로로든 알려 주기 바란다. 확인 후 반영하도록 하겠다.

 

이로서 27115번의 풀이를 마친다.