탈출

앞에서 풀지 못했던 스타트택시, 아기상어 때문에 자신감이 많이 떨어져있었지만, 다행히 이 문제는 한번에 풀 수 있었다. 이 문제가 비교적 쉬웠던건지 아니면 최근에 BFS연습 문제들을 푼 효과인진 모르겠지만, 자신감이 생겼다.🔥

문제 분석

지도 내에 고슴도치, 물, 비버 그리고 돌의 위치가 주어진다. 고슴도치는 물을 피해 비버의 보금자리로 도망가야 한다. 물은 매 분마다 인접해있는 칸으로 확장되고, 비버는 매 분마다 한 칸씩 움직이며 물을 피해간다. 지도 내에 돌이 위치하는데, 물과 고슴도치 둘다 돌이 있는 칸은 지나가지 못한다.

  • 물이 찰 예정인 칸으로는 고슴도치가 이동하지 못한다.

이때, 고슴도치가 물을 피해 비버의 보금자리까지 도달할 수 있다면, 도달하는데 걸리는 가장 빠른 시간을 출력하고, 도달할 수 없다면, ‘KAKTUS’를 출력한다.


기본적인 BFS와 달리, 물과 고슴도치가 번갈아 가며 움직여야 한다. 따라서, BFS를 돌며, deque에 바로바로 좌표들을 추가하는 것이 아니라 water_s, water_tmp 이렇게 두 리스트를 만들었다. water_s에서 popleft를 통해 원소들을 뽑으며 인접 칸들을 탐색하고, 그 칸들은 water_s에 바로 append되는 것이 아니라, water_tmp에 잠시 보관된다. water_s의 원소들이 모두 없어지면, 그때 water_tmp의 원소들이 water_s로 전달되고 ‘WATER’함수가 종료된다.

고슴도치가 해당 칸 까지 갈 수 있는 최단거리를 구하는 ‘KAKTUS’함수도 마찬가지다.


나머지 부분들은 모두 일반적인 BFS문제를 구현하듯 구현하면 문제 없을 것이다.


CODE

import sys
sys.stdin = open("input.txt","rt")
read=sys.stdin.readline
from collections import deque

r,c=map(int,read().split())
#r - 세로, c - 가로
map=list(list(read().strip()) for _ in range(r))
#비버 - D, 고슴도치 - S

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

water_s=deque([])
water_tmp=deque([])
kak_s=deque([])
kak_tmp=deque([])
D=[0,0]

for i in range(r):
    for j in range(c):
        if map[i][j]=='*':
            water_s.append([i,j])
        elif map[i][j]=='S':
            kak_s.append([i,j])
            map[i][j]=0
        elif map[i][j]=='D':
            D=[i,j]


def KAKTUS():
    while kak_s:
        a,b=kak_s.popleft()
        #print(a,b,map[a][b])
        for x,y in zip(dx,dy):
            ax=a+x
            by=b+y
            if 0<=ax<r and 0<=by<c and map[ax][by]==".":
                if map[a][b]=='*':
                    continue
                kak_tmp.append([ax,by])
                map[ax][by]=map[a][b]+1
            elif ax==D[0] and by==D[1]:
                if map[a][b]=='*':
                    print('KAKTUS')
                else: print(map[a][b]+1)
                sys.exit()
    for i in range(len(kak_tmp)):
        kak_s.append(kak_tmp.pop())


def WATER():
    while water_s:
        a,b=water_s.popleft()
        for x,y in zip(dx,dy):
            ax=a+x
            by=b+y
            if 0<=ax<r and 0<=by<c and (map[ax][by]!="X" and map[ax][by]!="D" and map[ax][by]!="*"):
                water_tmp.append([ax,by])
                map[ax][by]='*'
    for i in range(len(water_tmp)):
        water_s.append(water_tmp.pop())

while kak_s or water_s:
    KAKTUS()
    WATER()

print('KAKTUS')


다른 분들은 어떻게 풀었는지 한번 찾아봤다.

위에서 나는 물과 고슴도치가 번갈아가며 이동하게 하기 위해서 water_s, water_tmp와 같은 QUE두개를 이용했다. 그런데, 이렇게 배열을 두개 생성할 필요없이, 최초의 water_s 배열 길이를 저장해 놓고, 그 길이만큼만 원소들을 popleft하면 번갈아가며 이동하는 것을 구현가능했다.

다시 풀어볼때는 위의 방법으로 풀어보자.


[다시 풀어보기]