[BOJ] Q4179 불!

[BOJ] Q4179 불!

Question

Language: Python

Difficulty: Gold 4

처음에 해당 문제를 풀이할 때에는 지훈이의 현재 위치, 불의 좌표들을 활용하여 backtracking 방식으로 지훈이의 위치를 이동시키면서 최단거리를 구하려고 했지만, row,col이 최대 1000개까지 가능하기 때문에 시간 초과가 발생하게 되었다.

Fail Code

from math import inf
def solution(count,current_row,current_col,fires):
    global min_count

    #범위를 넘어서는 위치로의 이동 --> 밖으로 탈출 했음을 의미
    if current_row < 0 or current_row >=n_rows or current_col < 0 or current_col >=n_cols:
        min_count=min(min_count,count)
        return
    
    temp_fires=set()
    temp_board=board[:]

    #불을 퍼뜨린다.
    for row,col in fires:
        temp_fires.add((row,col))
        temp_board[row][col]="F"
        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]

            if next_row < 0 or next_row >= n_rows or next_col < 0 or next_col >=n_cols:
                continue

            if board[next_row][next_col]=="#":
                continue

            temp_fires.add((next_row,next_col))
            temp_board[next_row][next_col]="F"
    
    
    for dir in range(4):
        next_row=current_row + dy[dir]
        next_col=current_col + dx[dir]

        #범위를 벗어나는 경우 --> 탈출 가능
        if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col>=n_cols:
            solution(count+1, next_row, next_col,temp_fires)
            continue

        #불이 있는 경우
        if temp_board[next_row][next_col]=="F":
            continue
        #벽인 경우
        if temp_board[next_row][next_col]=="#":
            continue

        
        solution(count+1, next_row, next_col,temp_fires)
    
    return
        
if __name__ == "__main__":
    n_rows,n_cols=map(int,input().split())
    board=[list(input().strip()) for _ in range(n_rows)]
    min_count=inf

    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    fires=set()
    current_row,current_col=0,0
    for row in range(n_rows):
        for col in range(n_cols):
            if board[row][col]=="F":
                fires.add((row,col))
            if board[row][col]=="J":
                current_row,current_col=row,col
                board[row][col]="."
    solution(0,current_row,current_col,fires)
    print(min_count)

해당 문제는 bfs을 통해 풀이해야하는 문제이다.

불의 이동

우선 불을 먼저 이동시켜서 각각의 좌표에 불이 도달하기 까지의 시간이 어느정도 소요되는지 파악한다.

#각 좌표에 대해 불이 퍼지는데 걸리는 시간을 측정한다.
while fire_queue:
    row,col=fire_queue.popleft()

    for dir in range(4):
        next_row=row+dy[dir]
        next_col=col+dx[dir]

        #범위를 넘어서는 경우
        if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col>=n_cols:
            continue
        #이전에 방문한 위치인 경우
        if fire_visited[next_row][next_col] != -1:
            continue
        #벽인 경우
        if board[next_row][next_col] == "#":
            continue

        fire_visited[next_row][next_col]=fire_visited[row][col]+1
        fire_queue.append((next_row,next_col))

다음으로, 지훈이를 이동시켜서 지훈이가 해당 좌표에 불보다 먼저 도착할 수 있는 여부를 판단해서 지훈이를 이동시킨다.

지훈의 이동

#지훈이를 움직이면서 미로를 탈출할 수 있는 지 여부를 판단한다.
while jihoon_queue:
    row,col=jihoon_queue.popleft()

    for dir in range(4):
        next_row=row+dy[dir]
        next_col=col+dx[dir]

        #범위 밖으로 이동하는 경우는 미로를 탈출할 수 있는 경우이다.
        if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col>=n_cols:
            print(jihoon_visited[row][col]+1)
            return
        #이전에 방문한 경우
        if jihoon_visited[next_row][next_col] != -1:
            continue
        #벽인 경우
        if board[next_row][next_col] == "#":
            continue
        #지훈이 보다 불이 먼저 도착하는 경우
        if fire_visited[row][col] != -1 and jihoon_visited[row][col] +1 >= fire_visited[next_row][next_col]:
            continue

        jihoon_visited[next_row][next_col]=jihoon_visited[row][col]+1
        jihoon_queue.append((next_row,next_col))
        
print("IMPOSSIBLE")

Solution

from collections import deque
def solution():
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    fire_queue=deque()
    jihoon_queue=deque()

    fire_visited=[[-1]*n_cols for _ in range(n_rows)]
    jihoon_visited=[[-1]*n_cols for _ in range(n_rows)]

    for row in range(n_rows):
        for col in range(n_cols):
            if board[row][col]=="F":
                fire_visited[row][col]=0
                fire_queue.append((row,col))
            if board[row][col]=="J":
                jihoon_visited[row][col]=0
                jihoon_queue.append((row,col))
    
    #각 좌표에 대해 불이 퍼지는데 걸리는 시간을 측정한다.
    while fire_queue:
        row,col=fire_queue.popleft()

        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]

            #범위를 넘어서는 경우
            if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col>=n_cols:
                continue
            #이전에 방문한 위치인 경우
            if fire_visited[next_row][next_col] != -1:
                continue
            #벽인 경우
            if board[next_row][next_col] == "#":
                continue

            fire_visited[next_row][next_col]=fire_visited[row][col]+1
            fire_queue.append((next_row,next_col))

    #지훈이를 움직이면서 미로를 탈출할 수 있는 지 여부를 판단한다.
    while jihoon_queue:
        row,col=jihoon_queue.popleft()

        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]

            #범위 밖으로 이동하는 경우는 미로를 탈출할 수 있는 경우이다.
            if next_row < 0 or next_row >=n_rows or next_col < 0 or next_col>=n_cols:
                print(jihoon_visited[row][col]+1)
                return
            #이전에 방문한 경우
            if jihoon_visited[next_row][next_col] != -1:
                continue
            #벽인 경우
            if board[next_row][next_col] == "#":
                continue
            #지훈이 보다 불이 먼저 도착하는 경우
            if fire_visited[row][col] != -1 and jihoon_visited[row][col] +1 >= fire_visited[next_row][next_col]:
                continue

            jihoon_visited[next_row][next_col]=jihoon_visited[row][col]+1
            jihoon_queue.append((next_row,next_col))
            
    print("IMPOSSIBLE")
        
if __name__ == "__main__":
    n_rows,n_cols=map(int,input().split())
    board=[list(input().strip()) for _ in range(n_rows)]
    solution()