백준: 3055 탈출

 

문제

3055번: 탈출

 

문제 풀이

 고슴도치(S)가 비버의 굴(D)로 탈출 할 수 있는지를 찾는 문제이다. 다른 그래프 문제와 다른 점은 시간에 따라 물(*)이 비어 있는 칸으로 확장하는 것이다. 가만히 들여다 보면 어려운 문제는 아니고, 다음과 같은 처리가 필요하다는 것을 알 수 있다.

 

• 시간에 따라 물이 확장하는 경우
  • 물이 확장 하는 것은 토마토의 로직과 같이 구현하면 물이 퍼지는 상황을 구현 할 수 있다.
• 고슴 도치가 비버 굴로 가기 위한 방법
  • 다른 그래프 문제와 마찬가지로 BFS를 통해 상, 하, 좌, 우로 탐색하면 된다.
  • 하루 동안 일어 날 수 있는 경우의 수를 모두 처리하여야 하기 때문에, 상, 하, 좌, 우 중 접근 가능한 모든 경로를 같이 처리하여야 한다.

 즉, 어렵게 생각할 필요 없이 물이 확장하는 것 그래프를 만들면서 고슴 도치가 탈출 가능한지 판단하면 되는 2번의 BFS 탐색이 필요한 문제이다.

 

코드

from collections import deque
from sys import stdin


def visitable(x, y):
    return 0 <= x < n and 0 <= y < m


def bfs(start):
    flood()
    q = deque([start])

    while q:
        for _ in range(len(q)):
            cur_x, cur_y = q.popleft()

            for x, y in dirs:
                next_x = cur_x + x
                next_y = cur_y + y
                if visitable(next_x, next_y):
                    if graph[next_x][next_y] == '.' \
                            and not visited[next_x][next_y]:
                        visited[next_x][next_y] = visited[cur_x][cur_y] + 1
                        q.append([next_x, next_y])
                    elif graph[next_x][next_y] == 'D':
                        return visited[cur_x][cur_y]
        flood()

    return "KAKTUS"


def flood():
    for _ in range(len(water)):
        cur_x, cur_y = water.popleft()
        for x, y in dirs:
            next_x = cur_x + x
            next_y = cur_y + y
            if visitable(next_x, next_y) and graph[next_x][next_y] == '.':
                graph[next_x][next_y] = '*'
                water.append([next_x, next_y])


if __name__ == '__main__':
    X, Y = 0, 1
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    n, m = map(int, input().split())
    graph = []
    visited = [[0] * m for _ in range(n)]
    water = deque()

    for i in range(n):
        graph.append(list(stdin.readline().strip()))
        if 'S' in graph[i]:
            start = [i, graph[i].index('S')]
            visited[start[X]][start[Y]] = 1
        elif '*' in graph[i]:
            water.append([i, graph[i].index('*')])

    print(bfs(start))