[ baekjoon ] 탈출 3055번 ( python )

문제

백준 3055 탈출 풀이 ( 파이썬 )

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

3055번: 탈출

 

풀이

리스트 총 3개를 썼는데

하나는 기존 입력을 받는 리스트 (arr)

dist1은 물이 지나가면서 갈 수 있는 최소시간

dist2는 dist1과 arr를 보면서 dist1보다 작은 시간에만 이동할 수 있어야 지나칠 수 있다.

 

물길만을 따라가서 목적지에 도달하게하는 경우로 코드를 짤 경우 안 될만 테스트케이스는

10 15
........X......
..XXXXX.X.*....
X.....X.X..*...
.X.S..X.X......
D.X...X.XXXXXXX
.X....X........
.X....X.XXXXXXX
.XXXXXX.X......
........X......
XXXXXXXXX...*..

 

정답 : 30

 

인데 안되는 이유는 물길이 목적지를 갈 수 없는 경우이다. 

보면 물은 돌에 갇혀서 나올 수 없으므로 물이 D에 도달할 수 없다.

 

정답 코드는

from collections import deque

r,c=map(int,input().split())

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

dist1=[[-1]*c for _ in range(r)]
dist2=[[-1]*c for _ in range(r)]

for i in range(r):
    arr.append(list(map(str,input())))
    

water=deque()
place=deque()
dis=tuple()

for i in range(r):
    for j in range(c):
        if arr[i][j]=="*":
            water.append((i,j))
            dist1[i][j]=0
        if arr[i][j]=="S":
            place.append((i,j))
            dist2[i][j]=0
        if arr[i][j]=="D":
            dis=(i,j)
            
# 물에 대한 bfs
while water:
    x,y=water.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or ny<0 or nx>=r or ny>=c:
            continue
        if arr[nx][ny]=='X' or arr[nx][ny]=='D' or dist1[nx][ny]>=0:
            continue
        dist1[nx][ny]=dist1[x][y]+1
        water.append((nx,ny))
    

# 고슴도치 bfs
while place:
    x,y=place.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or ny<0 or nx>=r or ny>=c:
            continue
        if dist2[nx][ny]>=0 or arr[nx][ny]=='X':
            continue
        if dist1[nx][ny]!=-1 and dist1[nx][ny]<=dist2[x][ny]+1:
            continue
        dist2[nx][ny]=dist2[x][y]+1
        place.append((nx,ny))

# print(dist2)
if dist2[dis[0]][dis[1]]==-1:
    print("KAKTUS")
else:
    print(dist2[dis[0]][dis[1]])

 

비슷한 문제는

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

4179번: 불!