[BOJ]3055. 탈출

문제:

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

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

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

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

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

입력:

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

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

출력:

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

풀이방법:

 이 문제의 핵심은 물과 고슴도치의 이동을 BFS로 확인하면서 고슴도치가 비버의 집까지 갈 때까지 물의 영향을 받지 않는 지 확인해야 한다.

 우선 물에 대해서 BFS를 수행하면서 한 번 퍼질 때마다 1씩 늘어나면서 visit 배열이 채워진다. 이 때, 벽이나 비버의 집에는 물이 차지 않도록 한다.

 그 다음에는 고슴도치의 이동에 대해서 BFS를 수행하며 배열 안에 존재하며 비버의 집을 찾을 때 종료되도록 한다. 고슴도치가 이동할 때에는 물이 퍼진 정도에 따라 이동을 할 수 있으며, 물의 visit 배열 값보다 작을 때에만 이동할 수 있다. (물의 값이 4, 고슴도치가 이동할 값이 5라면 이동 불가 -> 물이 이미 차 있기 때문)

def main():
    from collections import deque
 
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
 
    r,c = map(int,input().split())
    hVisit = [[0 for _ in range(c)]for _ in range(r)]
    wVisit = [[0 for _ in range(c)]for _ in range(r)]
    forest = []
    Hedgehog = deque()
    water = deque()
    for i in range(r):
        temp = input()
        forest.append([])
        for j,t in enumerate(temp):
            if t == "X":
                forest[i].append(-1)
            elif t == "S":
                forest[i].append(1)
                Hedgehog.append((i,j))
                hVisit[i][j] = 1
            elif t == "*":
                forest[i].append(2)
                water.append((i,j))
                wVisit[i][j] = 1
            elif t == '.':
                forest[i].append(0)
            elif t == 'D':
                forest[i].append(3)
 
    while len(water):
        x,y = water.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if 0<=nx<r and 0<=ny<c and (forest[nx][ny]!=-1 and forest[nx][ny]!=3) and not wVisit[nx][ny]:
                water.append((nx,ny))
                wVisit[nx][ny] = wVisit[x][y] + 1
    while len(Hedgehog):
        x,y = Hedgehog.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<r and 0<=ny<c and forest[nx][ny]==3:
                print(hVisit[x][y])
                return 0
            if 0<=nx<r and 0<=ny<c:
                if forest[nx][ny] != -1 and not hVisit[nx][ny]:
                    if hVisit[x][y] + 1 < wVisit[nx][ny] or wVisit[nx][ny] == 0:
                        Hedgehog.append((nx,ny))
                        hVisit[nx][ny] = hVisit[x][y] +1
 
    print("KAKTUS")
    
if __name__ == "__main__":
    main()

문제링크:

www.acmicpc.net/problem/3055

3055번: 탈출