[알고리즘 문제 풀이][파이썬] 백준 5427번: 불

백준 5427 문제 링크: https://www.acmicpc.net/problem/5427

📑 문제 설명
1. 빈 공간과 벽으로 이루어진 건물에 화재 발생
2. 불은 매 초마다 동서남북 인접한 빈 공간으로 움직임(벽을 만나면 이동 불가)
3. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며 1초가 걸림
4. 상근이는 벽을 통과할 수 없으며 불이 옮겨진 칸 또는 붙으려는 칸으로 이동 불가
상근이가 이동함과 동시에 상근이가 있는 칸에 불이 붙는 건 가능
불이 이동했을 때 도착하는 칸과 상근이가 이동할 때 도착하는 칸이 일치하면 안됨
5. 빌딩 지도가 주어졌을 때 상근이가 빌딩을 탈출하는 최단 시간 구하기

입력: 첫째 줄에 테스트 케이스가 주어지며 각 테스트 케이스 첫째 줄에는 빌딩 지도의 너비와 높이 w, h가 주어진다 --> x방향으로 이동은 w, y방향으로 이동은 h
그 다음 h 줄에는 w개의 문자가 주어진다.
.: 빈 공간
#: 벽
@: 상근이의 시작 위치
*: 불
출력: 각 테스트 케이스마다 빌딩을 탈출하는데 최단 시간을 출력한다. 빌딩을 탈출할 수 없을 경우 "IMPOSSIBLE"을 출력한다.

💡 문제 해결 방법
알고리즘: BFS

알고리즘 선택 이유
1. 불은 동서남북을 고를 수 없고 시간이 흐를 때마다 넓게 옮겨짐
2. 불과 상근이를 동시에 처리해야 함
- 불의 이동 queue와 상근 이동 queue가 동시에 필요할까?
- 아니면 연구소3 문제처럼 불과 상근이의 위치를 모두 queue에 넣은 후 이동한 초가 같다면(한 영역에 상근과 불 도착 시간이 같다면) 상근이 이동 불가 --> 초를 저장하는 visit 배열 필요

또는 이 방법으로 풀고 성공
1. 불을 먼저 퍼뜨림(불 위치에서만 bfs)
2. 1번 bfs 완료 후 상근이 위치에서 출발할 때 빈 공간이거나 불이 옮겨진 곳에 time보다 이동시간이 작을 경우 방문 가능
3. 이동 가능 조건: 빈 공간(불이 도달하지 않은 공간) 이거나 불이 옮긴 시간보다 상근이의 이동시간이 더 적을 경우 방문 가능
4. 이동 불가 조건: 벽이거나 불이 옮긴 시간보다 상근이의 이동시간이 더 클 경우 방문 불가

예외처리 및 추가 내용
1. 탈출이라는 개념에 도착은 없기 때문에 w나 h를 벗어날 경우 탈출이라고 처리

스터디 내용
1. 다이나믹 그래프: 그래프 모양이 시시각각 바뀌는 그래프
2. time step 마다 동시에 움직이기 때문에 동시에를 해결해야 함
3. 불에 대한 bfs 처리 후 상근이 bfs 처리
4. 불: 벽 아니면 다 이동 가능
5. 상근: 벽, 불이 아니면 1번 이동 가능
6. outside 는 못 감 --> 상근이는 끝에 도달하면 탈출
7. front propagation 을 생각하여 풀기(동시에 다른 상태가 접근할 때 처리)

💻 코드

import sys
from collections import deque

# 0: 방문하지 않음 1: 상근이 방문함 2: 불이 방문함
def bfs(f_s, queue, visit): #불의 bfs인지 상근의 bfs인지 체크
    while (queue):
        x, y, time = queue.popleft()
        adjlist = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
        for nx, ny in adjlist:
            if nx >=0 and nx< h and ny >=0 and ny <w:
                if graph[nx][ny] == '.' or graph[nx][ny] == '@':
                    if visit[nx][ny] > time + 1:
                        visit[nx][ny] = time + 1
                        queue.append((nx, ny, visit[nx][ny]))
            elif f_s == 's':  # 상근이면 w, h를 벗어나는 순간 스탑
                print(time + 1)
                return
    if f_s == 's':
        print("IMPOSSIBLE")


tc = int(sys.stdin.readline())
for t in range(tc):
    w, h = list(map(int, sys.stdin.readline().split()))
    graph = [[0 for x in range(w)]for x in range(h)]
    visit = [[1e9 for x in range(w)]for x in range(h)]

    fqueue = deque()
    squeue = deque()
    for i in range(h):
        temp = sys.stdin.readline() # 공백이 없음
        for j in range(w):
            graph[i][j] = temp[j]
            if temp[j] == '@':
                squeue.append((i, j, 0))
            elif temp[j] == '*':
                visit[i][j] = 0
                fqueue.append((i, j, 0))
    # 불 먼저 bfs
    bfs('f', fqueue, visit)
    bfs('s', squeue, visit)

💟 추가적으로 알게 된 점