백준 3055 탈출 파이썬

www.acmicpc.net/problem/3055

3055번: 탈출

import sys
from collections import deque

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().rstrip().split())
    t_ddup_forest = []
    hedgehog_pos = []
    water_pos = deque()
    current_pos = [[False] * m for _ in range(n)]
    for i in range(n):
        l = list(sys.stdin.readline().rstrip())
        for j in range(len(l)):
            if l[j] == 'S':
                current_pos[i][j] = True
                hedgehog_pos.append((i, j))
            if l[j] == '*':
                water_pos.append((i, j))

        t_ddup_forest.append(l)


    def fill_water():
        global water_pos
        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        water_pos_size = len(water_pos)

        while water_pos and water_pos_size > 0:
            v, h = water_pos.popleft()
            water_pos_size -= 1
            for d in direction:

                nv, nh = v + d[0], h + d[1]
                if nv < 0 or nv >= n or nh < 0 or nh >= m:
                    continue
                if t_ddup_forest[nv][nh] == 'X' or t_ddup_forest[nv][nh] == 'D':
                    continue
                if current_pos[nv][nh]:
                    continue

                if t_ddup_forest[nv][nh] != 'X' and t_ddup_forest[nv][nh] != 'D' and t_ddup_forest[nv][nh] != '*':
                    water_pos.append((nv, nh))
                    t_ddup_forest[nv][nh] = '*'


    visited = [[0] * m for _ in range(n)]


    def move_beaver_home():
        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        q = deque(hedgehog_pos)

        while True:
            fill_water()
            q_size = len(q)
            if q_size == 0:
                return 'KAKTUS'
            while q and q_size > 0:
                v, h = q.popleft()
                q_size -= 1
                for d in direction:
                    nv, nh = v + d[0], h + d[1]
                    if nv < 0 or nv >= n or nh < 0 or nh >= m:
                        continue
                    if t_ddup_forest[nv][nh] == 'X' or t_ddup_forest[nv][nh] == '*':
                        continue

                    if t_ddup_forest[nv][nh] == 'D':
                        return visited[v][h] + 1

                    if t_ddup_forest[nv][nh] == '.' and not visited[nv][nh]:
                        visited[nv][nh] = visited[v][h] + 1
                        current_pos[v][h] = False
                        current_pos[nv][nh] = True

                        q.append((nv, nh))

        return 'KAKTUS'


    print(move_beaver_home())

 

아기상어를 풀고나서 자신감이 붙어서 '그런지 그리 어렵지 않을것 같은데?' 라며 덤벼들었다.

아무것도 보지 않고 풀어내기는 했으나 생각했던것보다 많은 시간이 소요돼서 기분이 썩 좋지는 않았다.

anyway,

이 문제의 핵심 아이디어는 

물을 한번 확장시킨후, 고슴도치가 이동가능 한 모든 경로를 bfs 로 구하는데 물 한번 확장에 고슴도치도 한번의 step 만 움직이도록 하는것이다.

즉, 물은 한번만 확장했는데 고슴도치는 bfs 를 통해서 쭉쭉쭉 이동해서 비버의 집까지 가버리면 안된다.

물 한번 확장할때 고슴도치 역시 한번만 이동하면 되는데 이 한번이라는게 상,하,좌,우에 이동가능한 한번의 스텝을 모두 고려하면 되며

이 과정을 반복하면 고슴도치가 비버의 집에 갈 수 있는지 없는지 알 수 있게 된다.

이 문제 풀때는 꽤 헤맨거같은데 지금보니 왜이리 쉬워보이지.. ;;

 

역시 DFS/BFS 가 그리디보다 쉬운것같다. 방법만 알면 나머지는 뭐 방문처리같은것만 잘 신경써주면 왠만하면 풀린다.