[bfs/백준] 5427번 : 불

- 문제 : https://www.acmicpc.net/problem/5427

 

문제 이해 

- 건물에서 불이 번져가는데, 상범이는 불에 닿지 않고 무사히 불을 탈출할 수 있는지 확인하는 문제다

- 상범이뿐만 아니라 불도 bfs로 진행되어야 한다. 그래서 초기 행렬 값을 입력 받을 때 불과 상범이의 위치, 타입을 queue에 입력 받아야 한다. (예 : [i, j, 'person'], [i, j, 'fire'])

- 각 초기 위치를 방문 처리해줘야 시간초과가 발생하지 않는다.

- 불이 번질 예정인 곳은 상범이가 못 가므로, 초기에 불의 위치를 모두 입력받은 다음 마지막에 상범이의 위치를 추가한다. 

- bfs를 진행하면서 상범이가 이동하는 것과 불이 이동하는 것을 구분해야한다. 상범이의 이동은 양의 정수로 +1 씩 하며 이동하고, 불이 이동하는 곳은 -1 처리한다. 

- 따로 탈출구가 명시되어 있지 않은데, 탈출구는 0행, n - 1행, 0열, m - 1열 중에 '.'인 어느 지점이든 탈출구가 될 수 있다. 

 

풀이 로직

- 여러 케이스가 있으므로 각 케이스마다 bfs를 진행한다. 

 

- 입력값(m, n, matrix)를 입력 받고 visit를 초기화 한다.

 

- 정답을 찾은 경우와 못 찾은 경우를 분리하기 위해 flag를 사용한다.

 

- 행렬값을 입력 받으면서 불의 위치와 타입('fire')을 queue에 입력하고 visit 값을 -1로 방문처리 한다. 상범의 위치는 person에 저장한 뒤 visit 값을 1로 방문처리 한다. 

 

- 불의 초기 위치를 모두 queue에 저장한 뒤 마지막으로 person의 위치와 타입('person')을 queue에 추가한다.

 

- while문으로 bfs를 수행하는데, 도착한 지점이 탈출구(탈출구는 0행, n - 1행, 0열, m - 1열 중에 '.'인 어느 지점)인 경우 visit[x][y]을 출력한 뒤 while문을 break한다. 

- 답을 찾지 못했다면 상하좌우로 다음 노드를 탐색하는데, 다음 조건을 만족하는 노드여야한다.

1. 방문하지 않았음

2. matrix의 값이 '.' 또는 '@'여야한다. (상범이는 '.'만 이동가능, 불은 '.', '@' 모두 이동가능한데 하나의 if문으로 처리하지 않으면 시간초과가 발생한다)

if not visit[nx][ny] and (matrix[nx][ny] == '@' or matrix[nx][ny] == '.'):

 

- 타입에 따라 visit 처리와 queue에 값을 삽입한다. 

 

- while문을 돌면서도 답을 찾지 못했다면 'IMPOSSIBLE'을 출력한다.

 

정답 풀이 

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    m, n = map(int, input().split())
    matrix = []
    queue = deque()
    person = ()
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    visit = [[0] * m for _ in range(n)]
    
    for i in range(n):
        matrix.append(list(input()))
        for j in range(m):
            if matrix[i][j] == '*':
                queue.append([i, j, 'fire'])
                visit[i][j] = -1
            if matrix[i][j] == '@':
                person = (i, j, 'person')
                visit[i][j] = 1
    queue.append(person)
    
    flag = False
    while queue:
        x, y, kind = queue.popleft()
        if x == 0 or x == n - 1 or y == 0 or y == m - 1:
            if kind == 'person':
                flag = True
                print(visit[x][y])
                break
            
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # kind가 person, fire인 경우 모두에 아래 조건을 적용해야 메모리 초과가 발생하지 않는다.
                if not visit[nx][ny] and (matrix[nx][ny] == '@' or matrix[nx][ny] == '.'):   
                    if kind == 'person':
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append([nx, ny, 'person'])
                    if kind == 'fire':
                        visit[nx][ny] = -1
                        queue.append([nx, ny, 'fire'])
    
    if flag == False:
        print('IMPOSSIBLE')

 

 

참고한 블로그 : 블로그