구현문제는 시간만 오래걸리지 쉽다는 편견을 깬 문제였다.
지금까지의 구현문제는 알고리즘만 떠올리면 시간초과는 신경쓸 필요가 거의 없었는데, 시간초과를 해결하기 위한 트릭? 테크닉?이 요구됐다.
처음에 제출한 코드는 이러하다.
import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
N,M = map(int,input().split())
lake = []
for i in range(N):
lake.append([*map(lambda x:-1 if x=="X" else 0 if x=="." else 1,input().strip())])
swan = []
dq = deque()
for y in range(N):
for x in range(M):
if lake[y][x]==1:
lake[y][x] = 0
swan.append((y,x))
elif lake[y][x]==-1:
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and lake[y1][x1]!=-1:
dq.append((y,x,1))
break
while dq:
y,x,time = dq.popleft()
if lake[y][x] != -1:
continue
maxtime = time
lake[y][x] = time
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and lake[y1][x1] == -1:
dq.append((y1,x1,time+1))
visited = [[0]*M for i in range(N)]
dq = deque()
dq.append((*swan[0],0))
result = maxtime+1
while dq:
y,x,time = dq.popleft()
if time >= result:
continue
if visited[y][x] and visited[y][x] <= time+1:
continue
visited[y][x] = time+1
if (y,x) == swan[1]:
result = min(result,time)
continue
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0:
if lake[y1][x1] <= time:
dq.append((y1,x1,time))
else:
dq.append((y1,x1,time+1))
print(result)요약하면
1. lake의 모든 좌표를 돌면서 백조를 찾고, 물과 닿아있는 얼음은 dq에 저장한다.
2. 물과 닿아있는 얼음에서부터 BFS를 실행하여 며칠이 지나야 얼음이 녹는지를 lake에 기록한다.
3. BFS를 실행, 이때 dq에는 y,x,time을 저장한다.
4. 현재의 time보다 작은 값일때는 지나가고, 클 경우에는 time을 +1해서 dq에 넣는다.
5. visited에 기록된 time이 현재의 time보다 클 경우 visited를 갱신할 수 있다. (멀리 돌아오더라도 더 작은 time값을 얻어야 하므로)
그러나 이 코드는 시간초과가 발생하였다. 이유를 추측해보건대 visited를 갱신하는 과정에서 중복해서 계산이 계속 일어나게 되고 시간초과가 빡빡하게 짜여진 이 문제 특성상 통과하지 못하는 것이었다.
이를 수정한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def BFS():
visited = [[0]*M for i in range(N)]
dq = deque()
newdq = deque()
dq.append(swan[0])
n = 0
while True:
while dq:
y,x = dq.popleft()
if visited[y][x]:
continue
visited[y][x] = 1
if (y,x) == swan[1]:
return n
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0:
if visited[y1][x1]:
continue
if lake[y1][x1] <= n:
dq.append((y1,x1))
else:
newdq.append((y1,x1))
dq = newdq
newdq = deque()
n += 1
N,M = map(int,input().split())
lake = []
for i in range(N):
lake.append([*map(lambda x:-1 if x=="X" else 0 if x=="." else 1,input().strip())])
swan = []
dq = deque()
for y in range(N):
for x in range(M):
if lake[y][x]==1:
lake[y][x] = 0
swan.append((y,x))
elif lake[y][x]==-1:
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and lake[y1][x1]!=-1:
dq.append((y,x,1))
break
while dq:
y,x,time = dq.popleft()
if lake[y][x] != -1:
continue
maxtime = time
lake[y][x] = time
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and lake[y1][x1] == -1:
dq.append((y1,x1,time+1))
print(BFS())요약하면,
1,2는 위와 동일
3. dq와 newdq 두개의 deque를 만든다.
4. 현재의 시간을 n으로 두고, 현재의 시간보다 작은곳을 탐사, 더 큰 지점을 만나면 newdq에 저장한다.
5. 백조와 만나면 값을 return하고, 만나지 못할 경우 n을 +1하고 BFS를 한번 더 실행한다, 이때 dq는 newdq를 이용한다.
dq를 두개로 분리해서 경계를 저장할 지점과 탐사할 지점으로 나누고 탐사가 종료되면 경계를 저장한 deque를 불러와 중복탐사를 방지하는 것이 알고리즘의 핵심이다.
오늘의 교훈) 중복탐사를 방지하자