[ 백준 3055 ] 탈출 - Python

문제 보기

이 문제는 bfs 문제이다.

 

물의 이동과 고슴도치의 이동 순서만 잘 고려해 준다면 어렵지 않게 풀 수 있다고 생각한다.

 

알고리즘의 순서는 아래와 같다.

1. 물의 이동을 수행한다.

2. 고슴도치가 이동할 수 있는 구간을 파악한 후 이동시킨다.

3. 1 ~ 2 의 과정을 도착지에 도달하거나, 더 이상 이동할 곳이 없을 때까지 진행한다.

 

코드

import sys
from collections import deque


def bfs():

    position = deque()  # 이동 경로
    water = deque()  # 물의 위치
    for i in range(R):
        for j in range(C):
            if arr[i][j] == "*":
                water.append([i, j])
            elif arr[i][j] == "S":
                position.append([i, j])

    cnt = 1
    while True:

        # 물 업데이트
        length = len(water)
        for i in range(length):
            row, col = water.popleft()
            if row - 1 >= 0 and arr[row - 1][col] == ".":  # 상
                arr[row - 1][col] = "*"
                water.append([row - 1, col])
            if row + 1 < R and arr[row + 1][col] == ".":   # 하
                arr[row + 1][col] = "*"
                water.append([row + 1, col])
            if col - 1 >= 0 and arr[row][col - 1] == ".":  # 좌
                arr[row][col - 1] = "*"
                water.append([row, col - 1])
            if col + 1 < C and arr[row][col + 1] == ".":   # 우
                arr[row][col + 1] = "*"
                water.append([row, col + 1])

        # 위치 업데이트
        length = len(position)
        if length == 0:
            return "KAKTUS"
        for i in range(length):
            row, col = position.popleft()
            if row - 1 >= 0 and arr[row - 1][col] == ".":  # 상
                arr[row - 1][col] = "S"
                position.append([row - 1, col])
            elif row - 1 >= 0 and arr[row - 1][col] == "D":
                return cnt
            if row + 1 < R and arr[row + 1][col] == ".":  # 하
                arr[row + 1][col] = "S"
                position.append([row + 1, col])
            elif row + 1 < R and arr[row + 1][col] == "D":
                return cnt
            if col - 1 >= 0 and arr[row][col - 1] == ".":  # 좌
                arr[row][col - 1] = "S"
                position.append([row, col - 1])
            elif col - 1 >= 0 and arr[row][col - 1] == "D":
                return cnt
            if col + 1 < C and arr[row][col + 1] == ".":  # 우
                arr[row][col + 1] = "S"
                position.append([row, col + 1])
            elif col + 1 < C and arr[row][col + 1] == "D":
                return cnt

        cnt += 1


if __name__ == "__main__":

    # input
    R, C = map(int, sys.stdin.readline().split())
    arr = [list(map(str, sys.stdin.readline().strip())) for _ in range(R)]

    # print
    print(bfs())