[백준/파이썬] 3055번 탈출

https://www.acmicpc.net/problem/3055

3055번: 탈출

문제 해석

 

물, 돌, 탈출구, 시작위치가 주어진다. 고슴도치는 상하좌우로 이동할 수 있고, 물과 돌이 존재하면 이동할 수 없다.

고슴도치의 이동이 끝난 뒤 물은 상하좌우로 번지게 되는데, 물은 돌, 탈출구로는 번질 수 없다.

추가적으로 고슴도치가 이동할 때 물이 번지게 될 위치로는 이동할 수 없다.

탈출구로 이동하기 위한 최소 시간을 구하는 문제이다.

---

코드

 

from collections import deque

# input
input = __import__('sys').stdin.readline
n, m = map(int, input().split())
arr = []
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

for i in range(n):
    arr.append(list(input().strip()))
    for j in range(m):
        if arr[i][j] == 'S':
            start = (i, j)
            arr[i][j] = '.'
        elif arr[i][j] == 'D':
            end = (i, j)
            arr[i][j] = '.'

def solve():
    global end
    ex, ey = end
    
    ans = 0
    q = deque()
    visit = [[0] * m for _ in range(n)]
    i, j = start
    q.append((i, j))
    visit[i][j] = 1
    while q:
        # 한 턴 동안 고슴도치의 다음 위치 탐색
        for _ in range(len(q)):  
            i, j = q.popleft()
            
            
            for k in range(4):
                x, y = i + dx[k], j + dy[k]
                if not(0 <= x < n and 0 <= y < m): continue
                if visit[x][y] == 0 and arr[x][y] == '.':
                    # 도착 지점인지
                    if x == ex and y == ey:
                        return ans + 1
                    # 다음 물이 차면 잠기는지 체크
                    flag = 1
                    for kk in range(4):
                        cx, cy = x + dx[kk], y + dy[kk]
                        if not(0 <= cx < n and 0 <= cy < m): continue
                        if arr[cx][cy] == '*': flag = 0
                    
                    if flag:
                        q.append((x, y))
                        visit[x][y] = 1
        
        water = []
        # 물 번지기
        for i in range(n):
            for j in range(m):
                if arr[i][j] == '*':
                    for k in range(4):
                        x, y = i + dx[k], j + dy[k]
                        if not(0 <= x < n and 0 <= y < m): continue
                        # 도착지점은 물 번지지 않도록 예외처리
                        if x == ex and y == ey: continue
                        if arr[x][y] == '.': water.append((x, y))
        
        for x, y in water:
            arr[x][y] = '*'
        
        ans += 1
        
    return "KAKTUS"

print(solve())

---

문제 풀이

 

항상 그래프 문제를 풀 때는 map의 시작위치와 종료위치 좌표를 딴 뒤 따로 저장하고 빈 칸으로 만들어 문제를 푼다. 

 

이 문제는 턴마다 구현을 해주어야 하는 문제이다. 따라서 BFS 큐에 크기만큼 popleft를 통해 그래프 탐색을 하고, 물을 번지도록 하도록 구현해주면 된다.

 

그래프 탐색에서는 해당 지점이 도착 지점인지 먼저 확인하고, 해당 지점 상하좌우에 물을 확인하여 물이 번지게 될 지점인지 예외처리를 해주었다.

이후 물을 번지도록 해야한다. 2중 for문을 통해 물이 존재하는 위치를 찾고, 해당 위치에 상하좌우에 물이 번질 수 있는지 확인한 뒤, 배열에 넣어주고 나중에 한꺼번에 갱신해주었다. 이때 번질 위치가 돌이거나, 탈출구일때를 잘 예외처리 해주었다.