[Baekjoon 3055 / python / 골드4] 탈출

# 도치가 사방으로 가는 것과, 물이 도치의 방문목록에 영향을 받는 것(도치가 지나간 길 안가는것)은 결과에 영향을 미치지 않는다.

import sys

from collections import deque

input = sys.stdin.readline

R, C = map(int, input().split())  # 행, 열

forest = [list(input().strip()) for _ in range(R)]

visited = [[-1] * C for _ in range(R)]  # -1로 설정해두고 도치의 이동 과정을 입력할것이다

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

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

queue = deque()

for x in range(R):

    for y in range(C):

        if forest[x][y] == '*':  # 물 좌표를 큐의 앞에 추가 ( 물이 먼저 가야 한다 )

            queue.appendleft((x, y))

        elif forest[x][y] == 'S': # 도치 좌표를 추가

            queue.append((x, y))

            visited[x][y] = 0  # 출발점에 걸린 시간 0 저장 -> 1씩 증가시키며 진행할것

def goingNogoing(x, y, visited, forest, who): # 갈지말지 판단하는 함수

    if 0 <= x < R and 0 <= y < C and visited[x][y] == -1 and forest[x][y] != 'X' and forest[x][y] != '*':

        if who == '*': # 물이면 다음곳이 비버집이면 안됨

            if forest[x][y] != 'D':

                return True

        else:

            return True

    return False

def killDochi():

    while queue:

        x, y = queue.popleft() # 물부터 나옴

        who = forest[x][y]  # 현재위치. 물 또는 도치가 들어있다.

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i] # 상하좌우로 반복해준다

            if goingNogoing(nx, ny, visited, forest, who):  # 갈수 있다면

                if forest[nx][ny] == 'D':  # 비버집 도착했으면 결과 출력

                    return visited[x][y] + 1

               

                visited[nx][ny] = visited[x][y] + 1  # 다음 진출경로에 시간 입력

                forest[nx][ny] = who  # 다음 칸을 도치/물로 변경 (진출한다)

                queue.append((nx, ny))

    return "KAKTUS"  # 숲을 다 돌았는데 비버집에 못 갔다면 KAKTUS 리턴

print(killDochi())

 

BFS 문제이다. 이것도 꽤 애를 먹었는데.. 물과 도치를 동시에 움직여야 하니 이걸 큐를 2개 써야하나 어째야 하나 고민을 많이 했다. 결국 큐 1개로 해결할 수 있었다.

 

물과 도치는 동시에 움직이지만, 코드에선 물이 먼저 움직이게 해야 도치가 물을 밟지 않게 할 수 있다. 따라서 while문을 시작하기 전에 주어진 물과 도치의 시작위치를 파악하여 큐에 넣어둔다. 이 때 appendleft를 사용하여 물이 먼저 pop되도록 큐의 끝쪽에 둬야 한다.

 

goingNogoing 함수는 물 또는 도치가 다음 좌표로 이동할 수 있는지 확인하는 함수이다. 좌표가 숲을 벗어나지 않으며 + 돌이 아니고 + 물도 아니고 + 미방문 상태여야 한다. 여기에 추가로 현재 이동하려는 애가 물이라면 비버집도 가지 못하게 한다. 이 모든걸 goingNogoing함수로 한번에 판단한다.

 

이후 반복문에서 상/하/좌/우를 탐색하며, 갈 수 있는 곳이라면 진출과 동시에 visited 좌표에 현재까지 걸린 시간을 입력해둔다.

만약 이동한 좌표가 비버집이라면 이전좌표까지의 값 + 1을 해서 리턴하고, 도착하지 못했다면 이전좌표까지의 값 + 1을 이동한 좌표에 입력한다. 그리고 큐에 다음 좌표를 추가한다.

 

이렇게 하면 물 도치 물 도치 물 도치 번갈아 가면서 이동하게 된다. 다만 고슴도치도 물처럼 사방으로 이동하고, 물은 고슴도치의 방문목록에 영향을 받아 도치가 갔던 곳은 가지 않는다. 하지만 이것은 결과에 영향을 미치지 않으니 문제는 없다.