5427번 - 불

💡 BFS 중 난이도가 많이 어렵고 시간이 오래걸린 문제이다.. 그래도 상세히 돌파하였다.

import sys
from collections import deque

# 함수 선언
def fire_bfs():
    
    while fire_dq:
        x, y = fire_dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if 0 <= nx < X and 0 <= ny < Y and graph[ny][nx] == '.' and visited_f[ny][nx] == 0:
                graph[ny][nx] = '*'
                visited_f[ny][nx] = visited_f[y][x] + 1
                fire_dq.append((nx,ny))

def sang_bfs():
    
    while sang_dq:
        x, y = sang_dq.popleft()
        
        if x == 0 or x == X-1 or y == 0 or y == Y-1:
            return visited_s[y][x]
        
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]

            if 0 <= nx < X and 0 <= ny < Y and graph[ny][nx] != '#' and visited_s[ny][nx] == 0:
                if graph[ny][nx] == '*' and visited_f[ny][nx] > visited_s[y][x] + 1:
                    visited_s[ny][nx] = visited_s[y][x] + 1
                    sang_dq.append((nx,ny))
                elif graph[ny][nx] == '.':
                    visited_s[ny][nx] = visited_s[y][x] + 1
                    sang_dq.append((nx,ny))
    
    return "IMPOSSIBLE"

# 입력 시작
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    
    X ,Y = map(int,input().split(' '))
    
    graph = [list(input().rstrip()) for _ in range(Y)]
    visited_f = [[0] * X for _ in range(Y)]
    visited_s = [[0] * X for _ in range(Y)]
    
    fire_dq = deque()
    sang_dq = deque()

    # 상하좌우
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    
    # 불, 상근넣기
    for i in range(Y):
        for j in range(X):
            if graph[i][j] == '@':
                sang_dq.append((j,i))
                visited_s[i][j] = 1
            elif graph[i][j] == '*':
                fire_dq.append((j,i))
                visited_f[i][j] = 1
                
    fire_bfs()
    print(sang_bfs())

• 이제 불 문제만 보면 구역질이 날것만 같다..ㅋㅋㅋㅋㅋ
• 기존 앞선 불! 포스팅과 동일한 문제였지만, 불!에서 기발했던 풀이 방식으로 다르게 풀어보았다.
• 불과 상근의 bfs함수를 따로 구현해서, 불을 아예 먼저 다 돌리고, 다음에 상근을 돌리는 방식으로 진행하였다.
• 핵심은 불을 먼저 다 돌리면서 걸린 날짜(이동하면 +1을 해준다)를 visited_f배열에 모두 저장을 하고 상근을 돌리면서 visited_f의 값과 visited_s 값을 비교해서 visited_s + 1이 작으면 fire보다 도달하는 날짜가 작은것이니 해당 경로는 갈 수 있음을 의미한다.
• 위 방식을 반복하면서 가장자리에 도달하면 탈출하며 return하는 방식을 사용하였다.

💡 문제가 되었던 반례

1) 처음 입장하자마자 탈출이 가능한 경우

1
2 2

[입력]
.@
..

answer:1

if x == 0 or x == X-1 or y == 0 or y == Y-1:
	return visited_s[y][x]

• 이 문제로 12%에서 약속처럼 오류가 발생하였다.
• 문제의 원인을 보자면 처음에 입장하자마자 탈출이 가능한 경우를 고려하고, 가장자리에 도달했을 경우를 대비하여 위와 같은 코드를 추가해서 해결하였다.

2) 코드의 오류 발견

1
4 3

[입력]
####
##@#
#*.#

answer = "IMPOSSIBLE"

if graph[ny][nx] -!= '#' and (nx == 0 or nx == X-1 or ny == 0 or ny == Y-1):
	return visited_s[y][x]

• 생각해보니 위의 코드가 있는데 For문 내부에 필요없는 중복코드가 있었고, 이것을 삭제하니 위의 반례도 통과되고 전체적으로 해결할 수 있었다.