[파이썬]백준 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))
알게된 것👨💻
- 코드가 중복될 경우 중복을 제거할 수 있는 방법을 생각해보자..
Author And Source
이 문제에 관하여([파이썬]백준 5427 불), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jajubal/파이썬백준-5427-불저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)