[백준/BOJ] gold4 - 3055번 탈출 (Python)

▶3055 - 탈출

백준 로고

▶문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해 보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해 있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

 

▶입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

 

▶출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

728x90

▶풀이

bfs만 사용해도 충분히 풀 수 있는 문제였다.

다른 bfs랑 똑같이 구성을 하면 되고, if문 안에 조건을 추가해 주면 된다.

if arr[x][y] == 'S' and (arr[nx][ny] == '.' or arr[nx][ny] == 'D'):
    arr[nx][ny] = 'S'
    visit[nx][ny] = visit[x][y] + 1
    queue.append((nx, ny))
elif arr[x][y] == '*' and (arr[nx][ny] == '.' or arr[nx][ny] == 'S'):
    arr[nx][ny] = '*'
    queue.append((nx, ny))

현재칸이 S이고 다음칸이 '.'이거나 D일 때는 S로 바꾸어주면 된다.

고슴도치가 이동하는 모습을 보여주기 위해서이다.

 

*일 때 다음칸이 '.'이거나 S라면 그 칸을 *로 바꾸어준다.

이는 홍수가 발생해 물이 넘치는 경우이고, 고슴도치가 물에 잠기기 때문에 없애주면 된다.

 

반복문을 돌리면서 D가 있는 칸이 S가 될 때 해당 값을 리턴해주면 된다.

while문이 종료된다면 D가 S가 되지 못했기 때문에 KAKTUS를 리턴해주면 된다.

from collections import deque


def bfs(Dx, Dy):
    while queue:
        if arr[Dx][Dy] == 'S':
            return visit[Dx][Dy]
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i] 
            if 0 <= nx < r and 0 <= ny < c:
                if arr[x][y] == 'S' and (arr[nx][ny] == '.' or arr[nx][ny] == 'D'):
                    arr[nx][ny] = 'S'
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append((nx, ny))
                elif arr[x][y] == '*' and (arr[nx][ny] == '.' or arr[nx][ny] == 'S'):
                    arr[nx][ny] = '*'
                    queue.append((nx, ny))
    return 'KAKTUS'


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

arr = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
visit = [[0 for _ in range(c)] for _ in range(r)]


for i in range(r):
    s = list(input().strip())
    arr.append(s)
    for j in range(c):
        if s[j] == 'S':
            queue.append((i, j))
        elif s[j] == 'D':
            Dx, Dy = i, j

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

print(bfs(Dx,Dy))

문제만 보면 처음에 어떻게 해야 하나 고민이 들었다.

queue를 두 개를 만들어서 할지 하나로 할지.

생각나는 대로 문제를 풀었고 이것이 정답이 되었다.

 

다른 bfs랑 크게 다를 것이 없어서 쉽게 풀렸던 것 같다.