🔥 불!

27 Jul 2022 in Algorithm on Bfs

백준 Gold4

불!

문제

---

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

---

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간 J는 입력에서 하나만 주어진다.

출력

---

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3

📖 알고리즘

문제에서 묻고자 하는 것은 미로에서 지훈이가 가장자리로 얼마나 빨리 도달할 수 있는지이다.

다시 말해, Weight가 없는 그래프가 주어지고 [특정 노드에서 특정 노드의 최단거리] 문제로 치환할 수 있다.

따라서 우리는 쉽게 BFS를 떠올릴 수 있다. 다만, 주의할 점은 지훈이 뿐만 아니라 불의 이동도 동시에 고려해주어야 한다는 점이다.

📐 설계

TRY 1, 시간 초과

지훈이와 불로부터 BFS를 출발하여 시간을 증가시켜준다. 그렇게 모든 BFS 탐색을 끝마치고 가장자리에 위치하며 벽과 불을 제외한 시간들 중에서 제일 작은 숫자를 뽑아서 출력한다. 이 때, 탈출하기 위한 마지막 1분도 포함되어 있으니 +1분을 해준다.

TRY 2, 메모리 초과

1트에서는 BFS 탐색 전부 끝마치고 시간을 찾았는데 2트에서는 while문 중간에 지훈이가 가장자리에 도달했을 경우 바로 탈출할 수 있도록 수정하였다.

# 지훈이 탈출 조건
        if (x == 0 or x == R-1 or y == 0 or y == C-1) and  who == 'J':
            return count[x][y] + 1

TRY 3, 정답

솔루션 참고: https://velog.io/@hygge/Python-백준-4179-불-BFS

메모리 초과가 나서 최대한 변수 사용을 줄였다. 아래는 2트에서 삭제한 변수들이다.

나름 줄인다고 줄였는데 더 이상 뭘 더 줄여야할지 몰라서 솔루션을 참고하였다. 😡

• 방문 여부 visited 배열
• 불과 지훈이를 판별하는 who
• 시간을 기록하는 time 배열
• 불의 위치를 담는 fire 배열

최대한 Queue 하나로 전부 해결할 수 있도록 하였다.

👨🏻‍💻 CODE

TRY 1

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

R,C = map(int,input().split())
maze = [] # 그래프
dx = [1,-1,0,0]
dy = [0,0,1,-1]
fire = [] # 불 위치
edge = [] # 가장자리

for i in range(R):
    maze.append(list(input().rstrip()))

# 지훈,불 위치 찾기
for i in range(R):
    for j in range(C):
        if maze[i][j] == 'J':
            j_x,j_y = (i,j)
        if maze[i][j] == 'F':
            fire.append((i,j))

# 최단 거리 찾기
def bfs(a,b):
    q = deque([])
    q.append([(a,b),'J'])
    for i in range(len(fire)):
        q.append([(fire[i][0],fire[i][1]),'F'])
    visited = [[False]*C for _ in range(R)]
    count = [[0]*C for _ in range(R)]

    while q:
        temp = q.popleft()
        x,y = temp[0]
        who = temp[1]

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if 0<=nx<R and 0<=ny<C and visited[nx][ny] == False and (nx,ny) not in fire:
                if maze[nx][ny] == '.':
                    if who == 'J': 
                        q.append([(nx,ny),'J'])
                        visited[nx][ny] = True
                        count[nx][ny] = count[x][y] + 1
                    if who == 'F':
                        q.append([(nx,ny),'F'])
                        fire.append((nx,ny))
    
    return count

distance = bfs(j_x,j_y)
answer = []
# 가장자리 최단거리
for i in range(R):
    if i == 0 or i == R-1:
        for j in range(C):
            if distance[i][j] > 0:
                answer.append(distance[i][j])
    else:
        if distance[i][0] > 0:
            answer.append(distance[i][0])
        if distance[i][C-1] > 0:
            answer.append(distance[i][C-1])

if not answer:
    print("IMPOSSIBLE")
else:
    print(min(answer)+1)

TRY 2

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

R,C = map(int,input().split())
maze = [] # 그래프
dx = [1,-1,0,0]
dy = [0,0,1,-1]
fire = [] # 불 위치
edge = [] # 가장자리

for i in range(R):
    maze.append(list(input().rstrip()))

# 지훈,불 위치 찾기
for i in range(R):
    for j in range(C):
        if maze[i][j] == 'J':
            j_x,j_y = (i,j)
        if maze[i][j] == 'F':
            fire.append((i,j))

# 최단 거리 찾기
def bfs(a,b):
    q = deque([])
    q.append([(a,b),'J'])
    for i in range(len(fire)):
        q.append([(fire[i][0],fire[i][1]),'F'])
    visited = [[False]*C for _ in range(R)]
    count = [[0]*C for _ in range(R)]

    while q:
        temp = q.popleft()
        x,y = temp[0]
        who = temp[1]

        # 지훈이 탈출 조건
        if (x == 0 or x == R-1 or y == 0 or y == C-1) and  who == 'J':
            return count[x][y] + 1

        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if 0<=nx<R and 0<=ny<C and visited[nx][ny] == False and maze[nx][ny] != '#':
                if who == 'J' and maze[nx][ny] == '.': 
                    q.append([(nx,ny),'J'])
                    visited[nx][ny] = True
                    count[nx][ny] = count[x][y] + 1
                if who == 'F' and maze[nx][ny] != 'F':
                    q.append([(nx,ny),'F'])
                    maze[nx][ny] == 'F'

    return None

count = bfs(j_x,j_y)

if count == None:
    print("IMPOSSIBLE")
else:
    print(count)

TRY 3

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

R,C = map(int,input().split())
maze = [] # 그래프
dx = [1,-1,0,0]
dy = [0,0,1,-1]

q = deque([])
for i in range(R):
    maze.append(list(input().rstrip()))
    # 지훈 위치 찾기
    if 'J' in maze[i]:
        q.append((i,maze[i].index('J'),0))

# 불 위치 찾기
for i in range(R):
    for j in range(C):
        if maze[i][j] == 'F':
            q.append((i,j,-1))

answer = "IMPOSSIBLE"

while q:
    x,y,time = q.popleft()

    # 지훈이 탈출 조건
    if (x == 0 or x == R-1 or y == 0 or y == C-1) and  maze[x][y] != 'F' and time > -1:
        answer = time + 1
        break

    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]

        if 0<=nx<R and 0<=ny<C and maze[nx][ny] != '#':
            # 지훈이
            if time > -1 and maze[nx][ny] == '.': 
                q.append((nx,ny,time+1))
                maze[nx][ny] = 'V'
            # 불
            elif time == -1 and maze[nx][ny] != 'F':
                q.append((nx,ny,-1))
                maze[nx][ny] = 'F'

print(answer)