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

문제

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

3055번: 탈출

 

코드

from collections import deque
r,c=map(int, input().split())

INF=int(1e10)

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

visited=[[0]*c for _ in range(r)]
array=[list(input().rstrip()) for _ in range(r)]
dr,dc=0,0

queue=deque()

for i in range(r):
    for j in range(c):
        if array[i][j]=='*':
            queue.append((i,j))

for i in range(r):
    for j in range(c):
        if array[i][j]=='S':
            queue.append((i,j))
        if array[i][j]=='D':
            dr,dc=i,j

while queue:
    x,y=queue.popleft()
    if dr==x and dc==y:
        break
    if array[x][y]=='*':
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<r and 0<=ny<c and array[nx][ny]!='X' and visited[nx][ny]==0 and array[nx][ny]!='D' and array[nx][ny]!='S':
                array[nx][ny]='*'
                visited[nx][ny]=INF
                queue.append((nx,ny))
    else:
        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 and array[nx][ny]!='*' and array[nx][ny]!='X':
                visited[nx][ny]=visited[x][y]+1
                queue.append((nx,ny))

if visited[dr][dc]==0 or visited[dr][dc]==INF:
    print("KAKTUS")
else:
    print(visited[dr][dc])