[파이썬]백준 5427 불

링크

백준 5427 불

bfs문제이다. 이 문제는 조금 복잡해 보이나 이것 하나만 잘 생각하면 된다.
상근이 뒤에 불이 붙는 것은 상관이 없고 상근이가 가는 길이 불로 막히는지 안막히는지만 판단하면 된다.
어차피 지나온 길은 다시 돌아갈 일이 없기 때문이다.

상근이의 움직임 보다 불을 먼저 움직여준 이유는 불이 붙을 예정인 자리론 이동할 수 없기 때문이다.

문제를 풀고 다른분이 푼 코드를 봤는데 나처럼 불과 상근이의 움직임을 따로 계산할 필요 없이 하나의 큐에 불을 먼저 넣어주는 방식으로 코드의 중복을 줄였다.
다음엔 좀더 코드의 중복을 줄이는 방법을 고민해봐야겠다.

정답 코드

from collections import deque
import sys

def bfs(start, fire):

    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]

    while start:
        for _ in range(len(fire)):
            fire_r, fire_c = fire.popleft()
            for j in range(4):
                fr = fire_r + dr[j]
                fc = fire_c + dc[j]
                if 0 <= fr < h and 0 <= fc < w: #범위체크
                    if building[fr][fc] == '.': #길이면 불이 번짐
                        building[fr][fc] = '*'
                        fire.append((fr, fc))

        for _ in range(len(start)):
            person_r, person_c = start.popleft()
            for i in range(4):
                nr = person_r + dr[i]
                nc = person_c + dc[i]
                if 0 <= nr < h and 0 <= nc < w: #범위안에 있을 때
                    if (nr == 0 or nr == h-1 or nc == 0 or nc == w-1) and building[nr][nc] == '.': #상근이가 끝에있고 그 끝이 갈수있으면
                        return building[person_r][person_c] + 1
                    if building[nr][nc] == '.':
                        building[nr][nc] = building[person_r][person_c] + 1 #상근이 이동
                        start.append((nr, nc))

    return 'IMPOSSIBLE'


for tc in range(int(sys.stdin.readline())):

    w, h = map(int, sys.stdin.readline().split())
    building = []
    start = deque()
    fire = deque()

    for i in range(h):
        tmp = list(sys.stdin.readline())
        building.append(tmp[:w]) #개행문자제거
        for j in range(w):
            if tmp[j] == '*':
                fire.append((i, j))
            if tmp[j] == '@':
                start.append((i, j))
                building[i][j] = 1 #초기값

    if start[0][0] == 0 or start[0][0] == h-1 or start[0][1] == 0 or start[0][1] == w-1: #끝에서 시작할 경우 코드가 작동을 안함
        print(1)
    else:
        print(bfs(start, fire))

알게된 것👨‍💻

• 코드가 중복될 경우 중복을 제거할 수 있는 방법을 생각해보자..