[백준 문제풀이] 얼렁뚱땅 3055 탈출 풀이

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

3055번: 탈출

 

# 물이 근처 상하좌우로 퍼짐
# 돌이나 물 없는 곳으로만 가야함
# 도치 -> 굴

from collections import deque

r, c = map(int,input().split())
arr = []
for i in range(r) :
    temp = list(map(str,input()))
    if 'D' in temp :
        j = temp.index('D') 
        bibeo = [i,j]
    if 'S' in temp :
        j = temp.index('S')
        dochi = [i,j]
    arr.append(temp)

q = deque()
# [좌표_x, 좌표_y, count]
q.append(dochi+[0])
precount = -1
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
min_ = 1000000000

while q :
    x, y, count = q.popleft()
    if [x,y] == bibeo :
        min_ = min(min_,count)
        break
    # 물 번짐
    
    if precount != count :
        visited = [[0] * c for _ in range(r)]
        for i in range(r) :
            for j in range(c) :
                if arr[i][j] == '*' and visited[i][j]==0 :
                    visited[i][j] = 1
                    for k in range(4) :
                        nx = i + dx[k]
                        ny = j + dy[k]
                        if 0<=nx<r and 0<=ny<c :
                            if arr[nx][ny] != 'D' and arr[nx][ny] != '*' and arr[nx][ny]!='X':
                                arr[nx][ny] = '*'
                                visited[nx][ny] = 1
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<r and 0<=ny<c :
            if arr[nx][ny] == '.' or arr[nx][ny] == 'D' :
                arr[nx][ny] = 'S'
                q.append([nx,ny,count+1])

    precount = count

if min_ == 1000000000 :
    print('KAKTUS')
else :
    print(min_)