https://www.acmicpc.net/problem/3197
3197번: 백조의 호수
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
www.acmicpc.net
처음엔 많이 풀어본 유형인듯 했으나 쉽게 풀리지 않았다.
시간 제한이 빡셌다.
<시간 초과 코드>
풀이 방식:
우선 백조가 만날 수 있는 지 여부는 bfs 탐색을 이용한다.
이때 q 리스트와 next_q 리스트를 사용했다.
37~51
일반적인 bfs처럼 q에서 원소하나씩을 빼서 조사를 하되, 빙판인 곳을 만나면('X') next_q에 이 좌표를 추가한다. 왜냐면 이 빙판은 어차피 다음 턴에 녹아있을 곳이다. 따라서 여기서 다시 bfs를 진행하면 된다. 이러면 처음부터 다시 bfs를 진행하는 일이 없게 된다. 재방문 방지를 위해 visited도 사용.
57~75
백조의 만남 여부를 체크한 후에는 빙판을 규칙에 맞게 녹여야 하는데,
나는 여기서 brute force로 빙판인 곳을 만나면('X') 동서남북 방향에 물('.')이 있는지 체크하고 물이 있다면 이 곳을 녹였다. 근데 여기서 바로 '.'으로 바꿔버리면 후에 다음 빙판을 조사할 때 물과 인접해있다고 오류를 범할 수 있기 때문에,
임시로 'M'으로 바꿨다가 나중에 다시 brute force로 '.'으로 바꿔줬다.
결론적으론 이런 brute force 때문에 타임아웃이 발생했다.
import sys
import collections
input = sys.stdin.readline
r, c = map(int, input().split())
graph = []
visited = [[0 for _ in range(c)] for _ in range(r)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# player's position
p1 = [0, 0]
p2 = [0, 0]
player_count = 0
for i in range(r):
row = [x for x in input()]
for j in range(c):
if row[j] == 'L':
row[j] = '.'
if player_count == 0:
player_count += 1
p1 = [i, j]
else:
p2 = [i, j]
graph.append(row)
q = collections.deque()
q.append(p1)
visited[p1[0]][p1[1]] = 1
answer = 0
next_q = collections.deque()
while True:
finish = False
next_q = collections.deque()
# check if meeting possible
while q:
x, y = q.popleft()
if [x, y] == p2: # reach!
finish = True
break
if graph[x][y] == 'X':
next_q.append([x, y])
continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<r and 0<=ny<c and visited[nx][ny] == 0:
visited[nx][ny] = 1
q.append([nx, ny])
if finish:
break
answer += 1
# iceberg is melt
for x in range(r):
for y in range(c):
if graph[x][y] == 'X':
melt = False
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<r and 0<=ny<c and graph[nx][ny]=='.':
melt = True
break
if melt:
graph[x][y] = 'M'
for x in range(r):
for y in range(c):
if graph[x][y] == 'M':
graph[x][y] = '.'
q = next_q
print(answer)
<정답 코드>
개선 방식:
백조 만남 여부에서 q와 next_q을 이용한 것처럼
빙판도 지금 녹는 곳뿐만 아니라 다음 턴에 녹을 곳을 미리 조사해놓기로 하였다.
30~43
녹는 곳의 정보를 담고 있는 melt_lst를 만들었다.
while문에 들어가기전, 한번의 brute force로 녹는 곳을 melt_lst에 추가시켜둔다. 이때 녹는 곳은 'M'으로 변경.
55
기존의 [if graph[x][y] == 'X':]을 [if graph[x][y] == 'M':]로 변경.
어차피 백조가 빙판을 만난다는건, 그 빙판은 이번에 녹을 것이기 때문이다.
70~79
이 부분이 사실상 이전 코드에 비해 시간 복잡도가 훨씬 줄어든 핵심이 된 부분이다.
melt_lst를 이미 구해놓았으므로 brute force가 필요없어졌다. melt_lst 원소를 하나씩 탐색하면서
그 위치의 동서남북을 탐색하여 주변에 'X'가 있다면 melt_lst에 추가시킨다. 이 추가된 곳들은 다음 턴에 녹을 곳이다.
이 녹을 곳을 'M'으로 바꿔준다. 동서남북 탐색이 끝났다면 현재위치는 '.'으로 바꿔준다. 이 곳은 이번에 녹았으니까.
(이번에 녹은 곳과 다음에 녹을 곳을 헷갈리면 안된다.)
import sys
import collections
input = sys.stdin.readline
r, c = map(int, input().split())
graph = []
visited = [[0 for _ in range(c)] for _ in range(r)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# player's position
player = []
for i in range(r):
row = [x for x in input()]
for j in range(c):
if row[j] == 'L':
row[j] = '.'
player.append([i, j])
graph.append(row)
q = collections.deque()
p1 = player.pop()
q.append([p1[0], p1[1]])
visited[p1[0]][p1[1]] = 1
answer = 0
next_q = collections.deque()
melt_lst = collections.deque()
for x in range(r):
for y in range(c):
if graph[x][y] == 'X':
melt = False
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] == '.':
melt_lst.append([x, y])
melt = True
break
if melt:
graph[x][y] = 'M'
while True:
finish = False
next_q = collections.deque()
# check if meeting possible
while q:
x, y = q.popleft()
if [x, y] == player[0]: # reach!
finish = True
break
if graph[x][y] == 'M':
next_q.append([x, y])
continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<r and 0<=ny<c and visited[nx][ny] == 0:
visited[nx][ny] = 1
q.append([nx, ny])
if finish:
break
answer += 1
# iceberg is melt
for _ in range(len(melt_lst)):
x, y = melt_lst.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] == 'X':
graph[nx][ny] = 'M'
melt_lst.append([nx, ny])
graph[x][y] = '.'
q = next_q
print(answer)
댓글