[백준/3055/파이썬] 탈출

https://www.acmicpc.net/problem/3055

3055번: 탈출

• 이 숲에는 도치가 있어요. 도치는 제일 친한 친구의 비버의 굴로 도망가려고 합니다.
• 티떱숲은 RC map입니다. 비어있는곳은 '.' , 물이 있는 지역은 '' , 돌은 'X' , 비버의 굴은 'D',고슴도치의 위치는 'S'로 나타내어져 있다.

불 문제랑 똑같은 메커니즘으로 생각하면 된다.

첫번째 solve는 불 문제랑 똑같이 시뮬레이션 형식으로 풀었다.

import sys
from collections import deque
input = sys.stdin.readline

R,C = map(int,input().split())
forest=[list(map(str,input().rstrip())) for _ in range(R)]
v_chk=[[0]*C for _ in range(R)]
dx=(0,1,0,-1)
dy=(1,0,-1,0)
wq=deque()
dq=deque()
def is_valid_coord(y,x):
    return 0<=y<R and 0<=x<C

def water():
    for _ in range(len(wq)):
        y,x=wq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if is_valid_coord(ny,nx) and forest[ny][nx] ==".":
                forest[ny][nx] ="*"
                wq.append((ny,nx))

def moving(y,x):
    v_chk[y][x] = 1
    dq.append((y,x))
    while dq:
        for _ in range(len(dq)):
            y,x= dq.popleft()
            for k in range(4):
                ny=y+dy[k]
                nx=x+dx[k]
                if is_valid_coord(ny,nx):
                    if v_chk[ny][nx] ==0 and forest[ny][nx] ==".":
                        v_chk[ny][nx] = v_chk[y][x] +1
                        dq.append((ny,nx))
                    elif forest[ny][nx] =="D":
                        print(v_chk[y][x])
                        return
        water()
        #for k in forest:
            #print(k)
    print("KAKTUS")
    return

for i in range(R):
    for j in range(C):
        if forest[i][j] =="S":
            sy,sx=i,j
            forest[i][j]="."
        if forest[i][j] =="*":
            wq.append((i,j))

water()
#for k in forest:
    #print(k)
moving(sy,sx)

두번째는,  이 문제를 다르게 푸는 방법을 찾아보려고, 여러 사람들의 블로그를 탐방했다.

- water의 거리를 표시하고, 그 거리와 도치가 간 거리를 비교해서, 조건을 나타내어 줬다.

- 메모리 공간은 밑에게 조금 더 잡아먹지만, 가독성이 매우 좋은 코드이다. 

from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
forest = [list(map(str,input().rstrip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

water = [[-1] * m for _ in range(n)]
q = deque()
for i in range(n):
    for j in range(m):
        if forest[i][j] == '*':
            q.append((i, j))
            water[i][j] = 0
        if forest[i][j] == 'S':
            go_y = i
            go_x = j
        if forest[i][j] == 'D':
            d_y = i
            d_x = j
while q:
    y, x = q.popleft()
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if 0 <= ny < n and 0 <= nx < m:
            if forest[ny][nx] =="." and water[ny][nx] == -1:
                q.append((ny, nx))
                water[ny][nx] = water[y][x] + 1


# 고슴도치 이동 시작
dist = [[-1] * m for _ in range(n)]
q = deque()
q.append((go_y, go_x))
dist[go_y][go_x] = 0

while q:
    y, x = q.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < n and 0 <= nx < m:
            # 돌이 아니고, 방문한 적이 없었던 곳 중에서
            if forest[ny][nx] != 'X' and dist[ny][nx] == -1:
                # 물이 아직 안 찼거나, 아예 차지 않는 곳이면 이동!
                if (dist[y][x] + 1) < water[ny][nx] or water[ny][nx] == -1:
                    q.append((ny, nx))
                    dist[ny][nx] = dist[y][x] + 1

#출력
if dist[d_y][d_x] == -1:
    print("KAKTUS")
else:
    print(dist[d_y][d_x])

다른 부분)

• dist[y][x] +1 < water[ny][nx]
• water는 물이 퍼지는 시간을 기록한 board인데, water[ny][nx] > dist[y][x] +1의 의미는 

물이 퍼지는 시간보다, 고슴도치가 거기에 도달하는 시간이 작다. 즉, 고슴도치가 빨리 도착한다. 이 말은, 물이 아직 퍼지지 않았다는 말이다.