[백준] 5427번. 불 🔥🔥

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

아이디어

• 저번에 풀었던 불!과 같은 아이디어로 풀었다.

  1. 상근이가 먼저 이동
  2. 불이 이동
  3. 가장자리에 오면 탈출

• 예외처리를 따로 해주지않고도 처리할 수 있는 방법을 찾아서 했는데 시간은 더 오래걸린다.
  • 아예 상근이 위치를 찾을 때 가장자리에 있으면 바로 탈출시키는 방법인데 따로 예외처리를 해줄 생각을 못할 수도 있으니까 탐색할 때 다음위치가 가장자리면 탈출
  • 근데 사실 별로 시간차이 안남..

시간 복잡도

• escape 코드 : O(w * h)
• 전체 코드 : O(t * w * h)

코드

• 처음 코드(예외 처리 따로한 코드)

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

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


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

            # 상근이
            if building[x][y] == '@':
                if 0 <= nx < h and 0 <= ny < w:
                    if building[nx][ny] == '.':
                        q.append((nx, ny, time + 1))
                        building[nx][ny] = '@'
                else:
                    return time + 1
            # 불
            else:
                if 0 <= nx < h and 0 <= ny < w and building[nx][ny] != '#' and building[nx][ny] != '*':
                    q.append((nx, ny, -1))
                    building[nx][ny] = '*'
    
    return "IMPOSSIBLE"


t = int(input())
for _ in range(t):
    w, h = map(int, input().split())

    building = [list(input().strip()) for _ in range(h)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([])
    time = 0

    # 위치 찾기
    for x in range(h):
        for y in range(w):
            # 상근이
            if building[x][y] == '@':
                # 바로 탈출 가능하면 탈출하기
                if not( 0 < x < (h - 1) and 0 < y < (w - 1)):
                    time = 1
                    break
                q.appendleft((x, y, 0))
            # 불
            elif  building[x][y] == '*':
                q.append((x, y, -1))
        if time > 0:
            break


    # 탈출하기
    if time == 0:
        time = escape()
    
    print(time)

• 예외 처리따로 안하고 합친 코드

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

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

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

            # 상근이
            if building[x][y] == '@':
                # 가장자리라서 바로 탈출 가능할 때
                if nx < 0 or ny < 0 or nx >= h or ny >= w:
                    return time + 1
                # 가장자리를 제외한 범위일 때
                elif 0 <= nx < h and 0 <= ny < w: 
                    if building[nx][ny] == '.':
                        q.append((nx, ny, time + 1))
                        building[nx][ny] = '@'
            # 불
            else:
                if 0 <= nx < h and 0 <= ny < w and building[nx][ny] != '#' and building[nx][ny] != '*':
                    q.append((nx, ny, -1))
                    building[nx][ny] = '*'
    
    return "IMPOSSIBLE"


t = int(input())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(t):
    w, h = map(int, input().split())
    building = [list(input().strip()) for _ in range(h)]
    q = deque([])
    
    # 위치 찾기
    for x in range(h):
        for y in range(w):
            # 상근이
            if building[x][y] == '@':
                q.appendleft((x, y, 0))
            # 불
            elif  building[x][y] == '*':
                q.append((x, y, -1))

    # 탈출하기
    print(escape())