[백준] 4179번. 불! 🔥

[백준] 번. 불! 🔥 바로가기

아이디어

• 백준 탈출을 생각하고 똑같이 구현했는데 예외 처리가 힘들었다. (10번만에 통과한듯) -> 실제 시험에서 테스트케이스없이 통과할 수 있을까? 🥺

아이디어

1. 지훈이와 불을 순서대로 queue에 담는다.
2. bfs를 한다.
   2-1. 지훈이일 때 이동가능한 곳을 찾고 이동한다 + 방문처리 겸 각 자리에서 나갈때까지 걸리는 시간을 더해준다(+1)
   2-2. 지훈이가 있는 곳이 벽이아닌 가장자리면 탈출 가능!
   2-3. 아니라면 다시 이동 반복.
3. 불도 벽이 아닌곳은 이동한다. -> 지훈이도 불로 먹을 수(?) 있음

문제점

1. 가장자리 범위 잘못설정
2. 불이 이동하기 전에 가장자리에 도착하면 갈수있다고 함 -> 일단 불의 이동까지 끝내고 내차례 때 가장자리인지 검사하기(가장자리 가기전에 불에 먹힐 수도 있으니까)
3. 시작부터 가장자리에 있으면 바로 탈출 가능

시간 복잡도

• O(r*c)

코드

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

# 탈출
def escape(position):
    while position:
        x, y = position.popleft()
        
        # 2. 지훈이는 미로의 가장자리에 접한 공간 살아남아서 갔을 때에만 탈출할 수 있다.
        if maze[x][y] == 'J' and not (1 <= x < r - 1 and 1 <= y < c - 1):
            return time[x][y] + 1
        
        # 이동
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            # 갈 수 있는 곳이면 이동
            if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] != '#':
                # 지훈이가 안갔던 곳이면
                if maze[x][y] == 'J' and maze[nx][ny] == '.' and maze[nx][ny] != 'J': 
                    time[nx][ny] = time[x][y] + 1 # 걸리는 시간

                    
                    position.append((nx, ny))    
                    maze[nx][ny] = 'J'            # 방문처리
                
                # 불!이고 안갔던 곳이면
                if maze[x][y] == 'F' and maze[nx][ny] != 'F':
                    position.append((nx, ny))
                    maze[nx][ny] = 'F'

    return "IMPOSSIBLE"


r, c = map(int, input().split())
maze = [list(input().strip()) for _ in range(r)]
time = [[0] * c for _ in range(r)]
position = deque([])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 지훈이의 위치와 불의 위치를 찾는다.
for i in range(r):
    for j in range(c):
        # 지훈이 먼저 넣기
        if maze[i][j] == 'J':
            # 3. 바로 탈출 가능하면 탈출하기
            if not (1 <= i < r - 1 and 1 <= j < c - 1):
                print(1)
                exit(0)
            position.appendleft((i, j))
        elif maze[i][j] == 'F':
            position.append((i, j))

# 탈출하러가기
print(escape(position))