오늘 풀어볼 문제는 탈출이다.
문제
풀이 과정
문제를 보고 처음 든 생각은 'BFS다'였다.
왜냐면 시작 지점부터 한칸씩 움직여가면서 도착지점까지 최소거리를 찾는 문제기 때문이다.
문제는 1초마다 물이 차오르는 것도 함께 고려해줘야 한다는 거다.
처음 생각한 아이디어는 아래와 같다(틀린 부분이 있다)
고슴도치가 bfs를 통해 움직이되 매번 고슴도치가 움직이기 전에 물이 차오르는 부분을 갱신해준다.
그 후에 고슴도치는 물이 차오르지 않은 부분으로만 이동한다.
실패코드
from collections import deque
def solution():
r, c = map(int, input().split())
roads = [[0 for j in range(c)] for i in range(r)]
dq = deque()
water = [] #현재 물이 차있는 곳의 좌표
visited = []
for i in range(r):
for j, elem in enumerate(input()):
# 고슴도치의 처음위치부터 bfs해야하니까 처음 위치 좌표 저장
if elem == "S":
dq.append((i, j, 0))
visited.append((i, j))
# 물이 차오르는 좌표 갱신을 위해 처음에 물이 차있는 곳들 좌표 저장
elif elem == "*":
water.append((i, j))
roads[i][j] = elem
dr = [0, 1, -1, 0]
dc = [-1, 0, 0, 1]
# 더이상 고슴도치가 갈 수 있는 좌표가 없을 때 까지 반복
while dq:
temp = []
# 현재까지 물이 차오른 곳을 돌면서
for (i, j) in water:
# 그 물이 차오른 곳의 주위(상하좌우)를 보면서
for _dr, _dc in zip(dr, dc):
nr = i + _dr
nc = j + _dc
# 물이 차지 않은 지역이면 물이 차오르도록 함
if 0 <= nr < r and 0 <= nc < c:
if roads[nr][nc] == ".":
roads[nr][nc] = "*"
# 다음 물이 차오를 곳의 위치를 정하기 위해 물이 새롭게 찬 지역을 저장
temp.append((nr, nc))
# 다음 번에는 이번에 새롭게 물이 찬 지역 근처의 지역이 잠길 것이므로 업데이트
water = temp[:]
i, j, count = dq.popleft()
# 도착지점까지 도착했으면 그때까지의 거리 리턴
if roads[i][j] == "D":
return count
# 고슴도치의 주위를 보면서
for _dr, _dc in zip(dr, dc):
nr = i + _dr
nc = j + _dc
if 0 <= nr < r and 0 <= nc < c:
# 다음으로 이동할 장소가 빈 공간이거나 도착 지점이면 이동
if roads[nr][nc] in [".", "D"] and (nr, nc) not in visited:
visited.append((nr, nc))
dq.append((nr, nc, count + 1))
# 다 이동 못했으면 KAKTUS 리턴
return "KAKTUS"
print(solution())이 코드로 예제도 통과했고, 자신만만하게 정답일 거라고 예상했는데 결과는 처참했다.
아무리 생각해도 맞는 거 같은데 뭐가 틀린거지? 하고 dq와 roads의 상태를 계속 찍어봤다.
그러니까 내가 간과한 부분이 보였다.
결론부터 말하자면 고슴도치가 움직이기 전에 매번 물이 차오르는 곳을 갱신한 게 문제다.
바보같은 실수였다. 물은 1초마다 차오르는 것이기 때문에 고슴도치의 움직임에 따라 갱신해선 안된다.
.....
..XXD
...XX
S....
....*
예를 들어서 이런 지도가 있다고 한다면
dq는 이렇게 갱신될 것이다.
처음
[(3, 0, 0)]
1초후
[(4, 0, 1), (2, 0, 1), (3, 1, 1)]
만약 물이 차오르는 곳을 저 실패코드대로 갱신한다면
(3, 0, 0) 일 때 1초후의 물이 차오른 지도를 보고,
(4, 0, 1)일 때는 2초후에 물이 차오른 지도를 보고,
(2, 0, 1)일 때는 3초후에 물이 차오른 지도를 보고,
(3, 1, 1)일 때는 4초후에 물이 차오른 지도를 보고 이동하게 된다.
하지만 생각해보면 [(3, 0, 0)]일 때는 1초후의 물이 차오른 지도를 보고,
나머지는 모두 2초 후의 물이 차오른 지도를 보고 이동해야 맞는 답이다.
이렇게 고슴도치가 여러군데로 이동하는 경우에 초가 달라질 수 있다는 걸 간과했다..
그래서 결론적으로는 고슴도치의 이동따로, 물의 이동 따로 총 두번의 bfs를 해줘야겠다고 생각했다.
어떻게 둘을 따로 계산하면서 고슴도치가 이동할 때 물이 차오른 정보를 줄 수 있을까 생각하다가
이전에 풀었던 토마토 문제가 생각났다.
여기서 지도에 직접 정보를 담아두는 방법이 있다는 걸 배웠는데 이걸 좀 응용하면 될 것 같았다.
즉, 주어진 지도에서 해당 좌표가 몇초후에 물에 잠기게 되는 지를 저장해두고
고슴도치는 현재 위치까지 오는데 몇초가 걸렸는 지를 알고 있으니
다음 위치에 적혀 있는 숫자가 다음 위치로 가는데 필요한 초(현재 초+1)이하면
이미 잠겼거나 다음에 잠길 땅이니 가지 않고, 아니면 이동하면 된다.
그러니까
D.*
...
..S
이런 지도가 있다고 했을 때
D 1 0
3 2 1
4 3 2
이런식으로 각 좌표가 몇초 후에 잠기는 땅인 지 저장해둔다.
처음에 고슴도치는
(2,2)위치에 있을 거고 주위를 보면 (2,1)이나 (1,2)가 있다.
(2,1) 땅에 적혀있는 값은 3이므로 3초후에 잠길 땅이다.
이 고슴도치는 현재까지 0초 움직였으므로 다음에는 1초 후에도 잠기지 않는 땅으로 가야한다.
3초후에 잠길 땅에 갈 수 있으니 큐에 넣는다.
(1,2) 땅에는 1이 적혀있으므로 1초 후에 잠길 땅이다.
이 고슴도치는 현재까지 0초 움직였으므로 다음에는 1초 후에도 잠기지 않는 땅을 가야한다.
하지만 (1,2)는 1초후에 잠기기 때문에 큐에 넣지 않는다.
...
정답코드
from collections import deque
def solution():
r, c = map(int, input().split())
roads = [[0 for j in range(c)] for i in range(r)]
dq = deque()
water_dq = deque() #현재 물이 차있는 곳의 좌표
visited = []
for i in range(r):
for j, elem in enumerate(input()):
roads[i][j] = elem
# 고슴도치의 처음위치부터 bfs해야하니까 처음 위치 좌표 저장
if elem == "S":
dq.append((i, j, 0))
visited.append((i, j))
# 물이 차오르는 좌표 갱신을 위해 처음에 물이 차있는 곳들 좌표 저장
elif elem == "*":
water_dq.append((i, j))
roads[i][j] = 0
dr = [0, 1, -1, 0]
dc = [-1, 0, 0, 1]
# 물이 각 좌표에 몇초 후에 차오르는 지 bfs로 계산
while water_dq:
# 현재 물이 차오른 위치
i, j = water_dq.popleft()
# 현재 위치에 물이 차오르기 시작한 초
sink_time = roads[i][j]
# 현재 물이 차오른 위치의 주변을 보면서
for _dr, _dc in zip(dr, dc):
nr = i + _dr
nc = j + _dc
if 0 <= nr < r and 0 <= nc < c:
# 빈 곳이면(X나 D인 곳은 물이 차오르지 못한다는 조건이 있으므로)
if roads[nr][nc] in [".", "S"]:
# 현재 초에서 1초 후에 이 위치가 물에 잠길 것
roads[nr][nc] = sink_time + 1
water_dq.append((nr, nc))
# 더이상 고슴도치가 갈 수 있는 좌표가 없을 때 까지 반복
while dq:
i, j, count = dq.popleft()
for _dr, _dc in zip(dr, dc):
nr = i + _dr
nc = j + _dc
if 0 <= nr < r and 0 <= nc < c:
if (nr, nc) not in visited:
# 도착지점까지 도착했으면 그때까지의 거리 계산해서 리턴
if roads[nr][nc] == "D":
return count + 1
# 다음으로 이동할 장소가 비어있거나 물이 차오르지 않은 곳이면 이동
if roads[nr][nc] == "." or (
type(roads[nr][nc]) == int and roads[nr][nc] > count + 1
):
visited.append((nr, nc))
dq.append((nr, nc, count + 1))
return "KAKTUS"
print(solution())이렇게해서 통과할 수 있었다.
다른 사람의 풀이
다른 사람의 풀이1
from collections import deque
R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
# 좌표 위에 뭔가 있으면 True로 방문 처리
visited = [[False] * C for _ in range(R)]
sonic = deque() # 고슴도치
water = deque() # 물
count = 0 # 시간(초) 카운트
# 방향 설정
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 물, 고슴도치 좌표 추가. 방문 True로 설정
for i in range(R):
for j in range(C):
if graph[i][j] == '*':
water.append((i, j))
visited[i][j] = True
elif graph[i][j] == 'S':
sonic.append((i, j))
visited[i][j] = True
elif graph[i][j] == 'X':
visited[i][j] = True
# 고슴도치 이동가능할때마다 반복문
while sonic:
# 물 현황 구현
for i in range(len(water)):
w_x, w_y = water.popleft()
for j in range(4):
nx = w_x + dx[j]
ny = w_y + dy[j]
if 0 <= nx < R and 0 <= ny < C:
if graph[nx][ny] == '.':
water.append((nx, ny))
graph[nx][ny] = '*'
visited[nx][ny] = True
# 물 확장시 시간 추가. 고슴도치는 물이 찰 예정 칸으로 이동할 수 없기 때문에 고슴도치 구현보다 먼저 카운트
count += 1
# 고슴도치 움직이는 로직 구현
for _ in range(len(sonic)):
s_x, s_y = sonic.popleft()
for i in range(4):
nx = s_x + dx[i]
ny = s_y + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if graph[nx][ny] =='.' and visited[nx][ny] == False:
sonic.append((nx, ny))
visited[nx][ny] = True
elif graph[nx][ny] == 'D':
print(count)
exit()
print('KAKTUS')이 방법은 내 첫번째 풀이와 비슷한데, 내 풀이의 문제점을 해결한 버전이다.
while 문 안에서 현재 큐의 길이만큼을 다 소진하고 다음으로 넘어가게 되면
1초씩 계산하는 셈이 될 수 있다는 걸 깨달았다.
다른 사람의 풀이2
from collections import deque
import sys
'''
@@@ 입력받기 @@@
'''
def input():
return sys.stdin.readline().rstrip()
R, C = map(int, input().split())
board = []
visited = [[False for _ in range(C)] for _ in range(R)]
for _ in range(R):
board.append(list(input()))
cnt = 0
success = False
q = deque([])
dir =[(-1,0),(1,0),(0,1),(0,-1)]
'''
@@@ 큐에 현재 물과 고슴도치를 넣어준다. @@@
- 반드시 물부터 넣어주어야함
'''
for r in range(R):
for c in range(C):
if board[r][c] == "*": # 물
q.append(("*", 0, r,c))
for r in range(R):
for c in range(C):
if board[r][c] == "S": # 고슴도치
q.append(("S", 0, r, c))
visited[r][c] = True
while q:
what, cnt, now_r, now_c = q.popleft()
for _r, _c in dir:
nxt_r, nxt_c = now_r + _r, now_c + _c
if not (0<=nxt_r<R) or not (0<=nxt_c<C):
continue
if what == "*": # 물
if board[nxt_r][nxt_c] == ".":
board[nxt_r][nxt_c] = "*" # 범람시키기
q.append((what, cnt+1, nxt_r, nxt_c))
else:
if visited[nxt_r][nxt_c]:
continue
if board[nxt_r][nxt_c] == ".": # 고슴도치
q.append((what, cnt+1, nxt_r, nxt_c))
visited[nxt_r][nxt_c] = True
elif board[nxt_r][nxt_c] == "D": # 굴 도착
success = True
break
if success:
break
if success:
print(cnt+1) # 도착전 cnt 의 + 1
else:
print("KAKTUS")신박한 풀이다. 큐를 하나만 써서도 풀 수 있구나...
하나의 큐에다가 물을 먼저 넣고 고슴도치 위치를 넣는 걸 반복하면 다른 사람의 풀이1처럼 동작하게 된다.
왜인지는 동작 방식을 생각해보면 간단하다.
처음에는 물이 차있는 위치를 모두 돌면서 지도에 1초 후에 물이 찰 위치에 표시를 해주고 큐에다 그 위치를 추가한다. 이렇게 1초후에 물이 찰 위치가 모두 표시된 후에야 고슴도치가 움직이게 된다. 고슴도치는 현재 지도에서 물이 차있지 않은 곳을 골라 이동하고 큐에다 그 위치를 추가한다. 즉 현재 고슴도치가 1초 후 갈 수 있는 위치를 모두 저장한다.
고슴도치 이동이 모두 끝난 후에는 앞과 똑같이 동작한다. 즉 지도에 2초 후에 물이 찰 위치가 표시되고 그 지도를 토대로 2초후에 갈 수 있는 위치가 큐에 추가된다....... 가 반복되는 것이다!
참고
https://dapsu-startup.tistory.com/entry/%EB%B0%B1%EC%A4%80-%ED%83%88%EC%B6%9C-3055-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython
https://programming119.tistory.com/209
