문제 링크
https://www.acmicpc.net/problem/3197
접근
가로와 세로의 길이가 최대 1500으로, 호수의 최대 크기는 대략 200만 정도가 된다.
사실 이 문제는 옛날에 c++로 도전했다가 시간초과를 맞은 문제다. 그때의 기억을 살려 이 문제를 풀 때 중요한 포인트를 생각했다.
중요하다고 생각하는 것은 2가지이다.
- 백조가 만날 수 있는지 여부를 매번 탐색하지 않는다.
- 녹을 가장자리의 위치를 미리 어딘가에 저정하자. 예상이 가능하다.
이 두가지를 기억하면 시간초과를 피할 수 있을 것이라 생각한다.
풀이
준비
우선은 기본 준비물이다.
r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]
root = [[(i, j) for j in range(c)] for i in range(r)]
rank = [[0 for j in range(c)] for i in range(r)] # union 최적화
visit = [[0 for _ in range(c)] for _ in range(r)]
swan = [] # swan[0] = (y1,x1), swan[1] = (y2,x2)
for i in range(r):
for j in range(c):
if board[i][j] == "L":
swan.append((i, j))
board[i][j] = "."
if len(swan) == 2:
break탐색을 편하게 하기 위해 백조의 위치를 따로 저장하고, 백조를 그냥 호수 물로(.) 취급하였다.
0일차 상태
그 다음은 처음 상태인 0일차 상태를 만들어 주는 것이다.
melt = deque()
for i in range(r):
for j in range(c):
if not visit[i][j] and board[i][j] == ".":
q = deque()
q.append((i, j))
visit[i][j] = 1
while q:
y, x = q.popleft()
root[y][x] = (i, j)
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] == ".":
visit[ny][nx] = 1
q.append((ny, nx))
elif (
in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] == "X"
):
visit[ny][nx] = 1
melt.append((ny, nx))호수 전체를 탐색하며 물이 있는 영역을 구분짓고, 녹을 가장자리를 큐 melt에 집어넣는다.
이때 물이 있는 영역은 분리집합을 생각하자. 여기서는 union-find 알고리즘을 사용하진 않았지만, root[y][x] = (i,j)와 같이 조건문에 처음 들어가게 한 위치를 그 영영의 root로 설정한다.
그렇게 되면 해당 영역에서 모두 한 곳(i,j)를 가리키므로 한 영역이라는 것임이 분명해진다.
1일차부터 얼음 녹기 시작!
이제 본격적인 알고리즘이다.
사실 큰 차이는 없지만... 아무튼 답을 구해보자.
day = 0
while find(swan[0]) != find(swan[1]):
tmp = deque() # 내일 녹을 얼음 위치
while melt:
y, x = melt.popleft()
board[y][x] = "."
merge_point = []
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] == "X":
visit[ny][nx] = 1
tmp.append((ny, nx))
elif in_range(ny, nx) and board[ny][nx] == ".":
merge_point.append((ny, nx))
for rt in merge_point:
if find(rt) != find((y, x)):
union(rt, (y, x))
melt = tmp
day += 1
print(day)우선 반복문은 백조가 만나지 못할 때 계속 반복된다.
큐 tmp는 다음날 녹을 얼음의 위치를 임시로 담아놓는 곳이다.
큐 melt에 대해 담겨있던 모든 녹을 얼음들의 위치를 꺼내본다.
그리고 그 얼음은 이제 녹았다고 생각하고, 해당 얼음의 상하좌우를 확인한다.
만약 인접한 곳에 얼음이 있으면 다음에 녹는다는 뜻이므로 큐 tmp에 넣고, 물이 있다면 union 한다.
그리고 마지막으로 내일 녹을 얼음들의 큐인 tmp를 melt로 바꿔준다.
정답 코드
안타깝게도 pthon3 로 제출했을 때는 시간초과가 나온다.
pypy로 제출하니 정답처리 되었다.
import sys
from collections import deque
#sys.setrecursionlimit(10 ** 8) # pypy 제출시 삭제!
input = lambda: sys.stdin.readline().rstrip()
in_range = lambda y, x: 0 <= y < r and 0 <= x < c
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
def find(v):
if v == root[v[0]][v[1]]:
return v
root[v[0]][v[1]] = find(root[v[0]][v[1]])
return root[v[0]][v[1]]
def union(v1, v2):
r1 = find(v1)
r2 = find(v2)
if rank[r1[0]][r1[1]] > rank[r2[0]][r2[1]]:
root[r2[0]][r2[1]] = r1
elif rank[r1[0]][r1[1]] < rank[r2[0]][r2[1]]:
root[r1[0]][r1[1]] = r2
else:
root[r2[0]][r2[1]] = r1
rank[r1[0]][r1[1]] += 1
r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]
root = [[(i, j) for j in range(c)] for i in range(r)]
rank = [[0 for j in range(c)] for i in range(r)] # union 최적화
visit = [[0 for _ in range(c)] for _ in range(r)]
swan = [] # swan[0] = (y1,x1), swan[1] = (y2,x2)
for i in range(r):
for j in range(c):
if board[i][j] == "L":
swan.append((i, j))
board[i][j] = "."
if len(swan) == 2:
break
melt = deque()
for i in range(r):
for j in range(c):
if not visit[i][j] and board[i][j] == ".":
q = deque()
q.append((i, j))
visit[i][j] = 1
while q:
y, x = q.popleft()
root[y][x] = (i, j)
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] == ".":
visit[ny][nx] = 1
q.append((ny, nx))
elif (
in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] == "X"
):
visit[ny][nx] = 1
melt.append((ny, nx))
day = 0
while find(swan[0]) != find(swan[1]):
tmp = deque()
while melt:
y, x = melt.popleft()
board[y][x] = "."
merge_point = []
for k in range(4):
ny, nx = y + dy[k], x + dx[k]
if in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] == "X":
visit[ny][nx] = 1
tmp.append((ny, nx))
elif in_range(ny, nx) and board[ny][nx] == ".":
merge_point.append((ny, nx))
for rt in merge_point:
if find(rt) != find((y, x)):
union(rt, (y, x))
melt = tmp
day += 1
print(day)
