3055번 탈출
https://www.acmicpc.net/problem/3055
아이디어
코드를 기능별로 구분하고 싶어서 함수를 4개 썼다.
- *인 물을 기준으로 몇 분만에 확장되는지 BFS를 돌린다.
- 고슴도치를 기준으로 BFS 돌릴 때 물이 채워져있으면 현재 시간이랑 물이 채워진 시간을 비교하여 물이 더 나중에 채워지면 고슴도치가 이동할 수 있다.
다음 4단계로 요약할 수 있다.
1) 물 위치를 찾는다.
def FindWater():
global water_queue
for i in range(R):
for j in range(C):
if graph[i][j] == '*':
water_queue.append([i, j])
graph[i][j] = 0 # 물 위치
return'*'의 위치들을 water_queue에 넣고 graph의 값을 0으로 바꿔준다.(BFS 돌리면서 +1씩 하기 위해)
2) 물 BFS
def BFSWater():
global water_queue
while water_queue:
x, y = water_queue.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx < 0 or nx >= R or ny <0 or ny >= C: continue
if graph[nx][ny] == '.':
graph[nx][ny] = graph[x][y] + 1
water_queue.append([nx, ny])
return상하좌우 돌면서 범위를 먼저 체크해주고 '.'인 경우에만 현재 물의 그래프 값에서 +1을 해준다.
이 함수를 다 돌고 나면 그래프에 있는 숫자들은 해당 칸이 몇 분 후에 물이 차오르는지 알 수 있다.
3. 고슴도치 위치 찾기
def FindHog(): # 고슴도치 위치 찾기
global queue
for i in range(R):
for j in range(C):
if graph[i][j] == 'S':
queue.append([i, j])
graph[i][j] = 0
visited[i][j] = True
return고슴도치의 위치를 찾아 그래프 값을 0으로 만들어주고 visited 2차원 배열을 만들어 방문했다는 표시로 True로 만들어준다.
이때 visited를 만든 이유는 물도 처음에 0으로 만들고 +1씩 해주기 때문에 고슴도치가 지나간건지 물이 차오른건지 몰라서 구분해주는 수단으로 사용을 했다.
4. 고슴도치 BFS
def BFSHog():
global queue
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= R or ny < 0 or ny >= C: continue
if graph[nx][ny] == '.':
graph[nx][ny] = graph[x][y] + 1
visited[nx][ny] = True
queue.append([nx, ny])
elif isinstance(graph[nx][ny], int) and not visited[nx][ny]: # 물이지나간자리면
if graph[nx][ny] > graph[x][y] + 1: # 물보다 작으므로 더 빨리 지나갈 수 있음
graph[nx][ny] = graph[x][y] + 1
visited[nx][ny] = True
queue.append([nx, ny])
elif graph[nx][ny] == 'D': # 도달
return graph[x][y] + 1
return 0먼저 고슴도치 위치를 기준으로 상하좌우를 돌면서 범위를 확인한다.
만약 그래프의 값이 '.'이면 물도 안 차오르는 경우이므로 현재 그래프의 값에서 +1을 하고 방문 처리를 한다.
만약 그래프의 값이 숫자이고 방문하지 않았다면 물이 차오른 경우이므로 원래 그래프에 있던 값과 현재 그래프 값에서 +1을 한 값을 비교해야한다.
그 이유는 원래 있던 그래프의 값은 물이 몇 분 후에 차오르는지이고 현재 그래프 값에서 +1을 한 것은 고슴도치가 몇 분 후에 가는지이다. 두 값을 비교하여 물의 값이 크면 즉, 원래 있던 값이 더 크면 물이 더 나중에 차오르는 경우이므로 그 값을 현재 그래프 값에서 +1을 하고 방문 처리를 한다.
여기서 내가 고려했던 것은 만약 그래프 값이 'D'이거나 'X'이면
if문을
if graph[nx][ny] > 0:이런식으로 했을 때 문자열이므로 에러가 난다.
그래서 그래프의 값이 int인지만 확인을 하면 된다.
if isinstance(graph[nx][ny], int):이렇게 하면 graph[nx][ny]가 int면 True, 아니면 False를 반환한다.
그리고 만약 'D'에 도달했으면 바로 현재 그래프 값에서 +1을 한 걸 리턴해주면 되고 while문을 끝까지 돌아도 'D'에 도달하지 않았다면 마지막에만 0을 리턴해주면 된다.
코드
import sys
from collections import deque
input = sys.stdin.readline
def FindWater():
global water_queue
for i in range(R):
for j in range(C):
if graph[i][j] == '*':
water_queue.append([i, j])
graph[i][j] = 0 # 물 위치
return
def BFSWater():
global water_queue
while water_queue:
x, y = water_queue.popleft()
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx < 0 or nx >= R or ny <0 or ny >= C: continue
if graph[nx][ny] == '.':
graph[nx][ny] = graph[x][y] + 1
water_queue.append([nx, ny])
return
def FindHog(): # 고슴도치 위치 찾기
global queue
for i in range(R):
for j in range(C):
if graph[i][j] == 'S':
queue.append([i, j])
graph[i][j] = 0
visited[i][j] = True
return
def BFSHog():
global queue
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= R or ny < 0 or ny >= C: continue
if graph[nx][ny] == '.':
graph[nx][ny] = graph[x][y] + 1
visited[nx][ny] = True
queue.append([nx, ny])
elif isinstance(graph[nx][ny], int) and not visited[nx][ny]: # 물이지나간자리면
if graph[nx][ny] > graph[x][y] + 1: # 물보다 작으므로 더 빨리 지나갈 수 있음
graph[nx][ny] = graph[x][y] + 1
visited[nx][ny] = True
queue.append([nx, ny])
elif graph[nx][ny] == 'D': # 도달
return graph[x][y] + 1
return 0
R, C = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(R)]
visited = [[False]*C for _ in range(R)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
water_queue = deque()
FindWater() # 물 위치 찾기
BFSWater() # 물 BFS
FindHog() # 고슴도치 위치 찾기
result = BFSHog() # 고슴도치 BFS
if result == 0:
print("KAKTUS")
else:
print(result)