미소를뿌리는감자의 코딩
[백준 2024/04/04] 7576번 토마토 본문
728x90
https://www.acmicpc.net/problem/7576
1. 접근 방법
이번 문제는 dfs가 아닌 bfs로 접근해야하는 문제라고 생각이 들었다.
같은 level에 위치한 값에 대해서, 좌우상하 퍼져나가는 것을 같은 시간대에 진행해야하기 때문이다.
만약 dfs로 진행한다면, 한 익은 토마토에 대해서 전체 박스에 퍼져나간 후, 다음 익은 토마토에 대한 코드를 진행하기 때문이다.
따라서 bfs로 재귀적으로 코드를 구성하고 문제를 푸니 recursion error가 발생하였다.
무언가 잘못 구성한 것 같은데 잘 모르겠어서, queue로 바꾸어서 풀었다.
이는 앞 문제, 1012번 유기농 배추와 같은 레파토리였다.
queue를 이용함으로서 에러가 나지 않고 해결할 수 있었다.
queue를 이용하여 재귀적으로 구성하지 않고도 풀이가 가능하다.
익은 토마토들을 파악한 후 이를 queue에 넣어준 후 함수로 보내준다.
queue가 빌 때까지 while문을 돌린 후, 현재 queue값을 기준으로 pop을 진행한다.
만약 처음 익은 토마토가 2개였다면 for문은 2번 돌리게 될 것이다. 2번 돌리면서, 해당 익은 토마토를 기준으로 상하좌우를 확인하고,
이중 리스트 기준 안에 있고 0이라면, 해당 값을 1로 바꾸어주었다.
이렇게 진행한 후 queue가 비게 된 다는 것은 더 이상 접근할 토마토가 없는 것이므로 days를 반환해준다.
2. 코드
from collections import deque
def bfs():
days = -1
while queue:
days += 1
for _ in range(len(queue)):
x, y = queue.popleft()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and tomato[nx][ny] == 0:
tomato[nx][ny] = 1
queue.append((nx, ny))
return days
def check_zero():
for x in range(m):
for y in range(n):
if tomato[x][y] == 0:
return True
return False
n, m = map(int, input().split())
tomato = []
for _ in range(m):
line = list(map(int, input().split()))
tomato.append(line)
queue = deque()
for x in range(m):
for y in range(n):
if tomato[x][y] == 1:
queue.append((x, y))
answer = bfs()
if check_zero():
print(-1)
else:
print(answer)
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/04/16] 2110번 공유기 설치 (0) | 2024.04.16 |
---|---|
[백준 2024/04/03] 9663번 N-Queen (0) | 2024.04.05 |
[백준 2024/04/05] 1012번 유기농 배추 (0) | 2024.04.05 |
[백준 2024/03/29] 15650번 N과 M (2) (0) | 2024.03.29 |
[백준 2024/03/28] 2630번 색종이 만들기 (0) | 2024.03.28 |