[백준 5427] 불

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

5427번: 불

 

 

from collections import deque
import sys

input = sys.stdin.readline

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


def bfs():
    while q:
        x, y = q.popleft()
        now_state = visited[x][y] # 현재 좌표의 상태를 저장. 불이라면 FIRE, 상근이면 이동횟수가 저장됨. 

        for i in range(4): # 상하좌우 돌기 
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < h and 0 <= ny < w: # 좌표 범위 안이고,
                # 아직 방문하지 않았고, 빈 곳이거나 상근이 시작점이라면, 
                if visited[nx][ny] == -1 and (board[nx][ny] == "." or board[nx][ny] == "@"):
                    if now_state == "FIRE": # 현재 상태가 불이라면 인근 상하좌우도 불이 붙음 
                        visited[nx][ny] = now_state
                    else: # 현재 상태가 상근이의 이동횟수라면 횟수를 1 올려서 저장 
                        visited[nx][ny] = now_state + 1
                    q.append((nx, ny)) # 큐에 인근 좌표값 저장 
            else: # 좌표 범위를 벗어났고, 상근이라면 탈출했다는 뜻이므로 탈출 1칸을 더해 이동 횟수 리턴
                if visited[x][y] != "FIRE":
                    return visited[x][y] + 1

    return "IMPOSSIBLE" # 상근이가 탈출하지 못했으므로 IMPOSSIBLE 리턴 


t = int(input()) # 테스트 케이스 입력 

for _ in range(t): # 테스트 케이스 돌리기 
    w, h = map(int, input().split())
    q = deque() # BFS 큐용 
    board = [] # 입력 좌표 받기용 
    visited = [[-1] * w for _ in range(h)] # 방문한 좌표 표시를 위한 2차원 배열, 아직 안 간 곳은 -1
    
    for i in range(h):
        board.append(list(input().strip())) # 각 줄을 입력으로 받고, 문자 단위로 배열로 넣기 
        for j in range(w): # 받은 배열중 상근이와 불의 시작점을 BFS 큐에 넣기 
            if board[i][j] == "@": # 상근이 시작점이면 방문 표시 및 큐 시작점으로 저장 
                visited[i][j] = 0
                start = (i, j) # 불이 먼저 퍼져야 하므로 큐에 아직 넣지 않음 
            elif board[i][j] == "*": # 불의 시작점이면 visited에 불이라고 표시 후 큐에 넣기 
                visited[i][j] = "FIRE"
                q.append((i, j))

    q.append(start) # 상근이를 큐의 가장 마지막에 넣은 후 
    print(bfs()) # BFS 시작

 

먼저 아랫쪽 입력받는 부분부터 보면, 전형적인 BFS 답게 큐와 방문좌표를 만들어주고 입력좌표를 돌면서 체크지점들을 발견시 큐에 넣어주고 있다. 

 

그중에 불을 발견하면 바로 큐에 넣어주는 반면, 상근이(@)를 발견하면 큐에 바로 넣지 않고 시작점을 따로 저장해두었다가 입력좌표를 전부 돌고 난 후에 큐에 넣어주는 것을 볼 수 있다. 

 

이는 문제에서 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 상근이가 움직일 수 없다는 조건 때문에 그렇다. 

불1			상근1

 

			상근2
불1		상근2	상근1
			상근2

 

불2			상근2
불1	불2	상근2	상근1
불2			상근2

 

불2		상근3	상근2
불1	불2	상근2	상근1
불2		상근3	상근2

 

불2	불3	상근3	상근2
불1	불2	불3	상근1
불2	불3	상근3	상근2

 

위 표는 상근->불 순서대로 진행했을 때를 나타낸 표인데, 밑의 2개의 표에서 3초 시점에서는 "불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로는 상근이가 이동할 수 없다" 라는 조건 때문에 2행 3열의 상근2는 불에 타서 죽게 되어 그 위아래의 상근3은 없어야 한다. 

따라서 불->상근 순서대로 BFS를 돌려야 문제 조건에 맞게 풀 수 있다. 

 

불(1)

불(2)

상근

불(1)의 상하좌우

불(2)의 상하좌우

상근의 상하좌우

...이후 진행

입력좌표에서 불이2개 있었다고 가정하면, BFS 큐의 관점에서 보면 불1->불2->상근->불1의 상하좌우로 불이 번짐->불2가 번짐->상근이 이동 ... 이렇게 진행되게 된다. 

 

또 BFS 함수에서는, now_state 라는 변수에다가 visited 에 저장된 현재 좌표의 상태를 저장했는데, 불이 번진거라면 FIRE가, 아니라면 상근이의 이동횟수가 저장이 된다. 

 

그리고 현재 좌표의 상하좌우로 인근 좌표를 탐색하는데, 좌표 범위 안의 값이고 방문하지 않았으며, 빈칸이거나 상근이의 시작점일 때, 현재 상태가 불이라면 그 상하좌우도 불이 옮겨 붙고, 상근이라면 이동횟수를 1 올려서 상태를 저장한다. 

 

그리고 좌표 범위 밖이고 상근이라면(불이 아니라면) 상근이가 탈출했다는 뜻이므로 탈출하는데 필요한 1칸을 올려서 리턴을 해준다. 

 

만약 BFS를 다 돌려도 상근이가 탈출하지 못했다면 IMPOSSIBLE 을 리턴해준다. 

 

참고자료

https://velog.io/@ckstn0778/%EB%B0%B1%EC%A4%80-5427%EB%B2%88-%EB%B6%88-O-1-Python

백준 5427번 - 불(★★★ / O / 1) : Python

마지막 추천코드를 참고했다.