[백준] 5427번: 불 - 파이썬

🔈 문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

 

📝입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불

각 지도에 @의 개수는 하나이다.

 

📑출력

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

 

📚 문제 풀이

 

흔히 볼 수 있는 BFS 문제의 유형이였다.

A에서 B로 갈 때의 소요시간을 구하는 문제였고, A는 @의 위치 그리고 B는 #이 아닌 가장자리이다.

다만 불이라는 변수가 있었다. 불이 붙은 곳은 이동할 수 없었고, 이 경우를 같이 확인해줘야 했다.

 

불이 붙는 경로와 상근이의 이동 경로를 실시간으로 확인하려고 하니 조금 복잡해졌다. 그래서 먼저 불을 지르고 상근이를 이동시켰다. 즉 각 경로마다 불이 붙는 시간을 체크해둔뒤 상근이가 그 지점에 오는 시간과 비교하여 상근이가 지나갈 수 있는 곳인지 아닌지를 파악하였다.

 

불의 초기 위치를 큐에 삽입하고 BFS를 통해 '#'을 빼고 불을 질렀다.

불이 붙은 시간이 담긴 배열을 갖고 이제 상근이를 움직였다.

상근이가 이동할 수 있는 경로는 '#'이 아니고 불이 붙은 시간보다 상근이가 더 빨리 도착한 경우이다.

 

💻 코드

from collections import deque
import sys
input = sys.stdin.readline
 
dx = [0,1,-1,0]
dy = [1,0,0,-1]
 
# 불 지르기
def burn():
    while queue:
        x,y,t = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위 밖이라면
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            # 벽이 아니고 방문하지 않았다면
            if graph[nx][ny] != '#' and visited[nx][ny] == 0:
                visited[nx][ny] = t + 1
                queue.append([nx,ny,t+1])
    return visited
 
# 상근이 이동
def bfs(a,b):
    q = deque()
    q.append([a,b,1])
    while q:
        x,y,c = q.popleft()
        # 탈출했다면 
        if x == h-1 or y == w-1 or x == 0 or y == 0:
            return c
 
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            # 범위 밖이라면
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            # 벽이 아니라면
            if graph[nx][ny] != '#':
                # 불이 붙기 전에 이동하거나 아예 불이 붙지 않는 곳이라면 방문
                if c+1 < visit[nx][ny] and visit[nx][ny] != -1 or visit[nx][ny]==0:
                    q.append([nx,ny,c+1])
                    visit[nx][ny] = -1
    
    # 루프문 끝났는데도 탈출하지 못했다면 
    return 'IMPOSSIBLE'
 
for _ in range(int(input())):
    w,h = map(int,input().split())
    graph = [list(map(str,input().rstrip())) for _ in range(h)]
    # 불이 붙은 위치 담을 큐
    queue = deque()
    visited = [[0]*(w) for _ in range(h)]
    for i in range(h):
        for j in range(w):
            # 해당 구역에 불이 붙었다면 큐에 좌표 삽입
            if graph[i][j] == '*':
                queue.append([i,j,1])
                visited[i][j] = 1
            # 상근이가 
            elif graph[i][j] == '@':
                sx,sy = i,j
    visit = burn()
 
    print(bfs(sx,sy))

 

🍭 시행착오

25프로...ㅎ

문제의 아이디어를 얻어내는대 조금 시간이 걸렸다..ㅋㅋㅋ(앞에서는 흔히 볼 수 있는 BFS라며)

🔗 문제링크 불

5427번: 불