python 백준 3055번 탈출

백준 문제 3055번

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

3055번: 탈출

 

import sys
from collections import deque

r,c = map(int,sys.stdin.readline().split())
matrix = []
## 도치의 위치 ##
S_loca = []
## 물의 위치들 ##
water_loca = []
queue = deque()
## 물의 위치와 도치의 위치를 찾는다 ##
for x in range(r):
    temp = []
    count = 0
    for y in sys.stdin.readline().rstrip():
        temp.append(y)
        if y == 'S':
            S_loca.append([x,count,'S'])
        elif y == '*':
            water_loca.append([x,count,'W'])
        count += 1
    matrix.append(temp)
## 날짜를 세주기 위해 도치를 1로 바꾼다 ##
matrix[S_loca[0][0]][S_loca[0][1]] = 1

def bfs():
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while queue:
        y,x,check = queue.popleft()
## 도치와 물의 주변 탐색 ##
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx<0 or ny<0 or nx>=c or ny>=r:
                continue
			## '.'이면 도치 or 물 이동 ##
            if matrix[ny][nx] == '.':
            ## 도치일 경우는 날짜를 더해준다 ##
                if check == 'S':
                    matrix[ny][nx] = matrix[y][x] + 1
                    queue.append([ny,nx,'S'])
           ## 물일 경우 덮어 씌운다 ##
                elif check == 'W':
                    matrix[ny][nx] = '*'
                    queue.append([ny,nx,'W'])
            elif matrix[ny][nx] == '*':
                continue
            elif matrix[ny][nx] == 'X':
                continue
           ## queue 상태를 check해주어 도치가 D(비버굴)의 도착했을 경우 게임을 끝낸다 ##
            elif matrix[ny][nx] == 'D' and check == 'S':
                matrix[ny][nx] = matrix[y][x] + 1
          ## 날짜가 지나는 개념이기 때문에  -1을 해줌 ##
                return matrix[ny][nx] -1
    ## 도치가 D 비버굴을 찾지못하면 KAKTUS를 리턴해준다 ##
    return 'KAKTUS'
## 물이 먼저 이동해주어야 되므로 queue에 물에 위치값을 먼저 리턴해준다 ##
## water loca = [x,y,'w']
## 도치 loca = [x,y,'s'] 로 구성되어 있다
for asd in water_loca:
    queue.append(asd)
for asd in S_loca:
    queue.append(asd)


print(bfs())