728x90
반응형
링크: https://www.acmicpc.net/problem/7576
아이디어
- 익은 토마토(1)의 좌표들를 q에 넣고 bfs
- 숨바꼭질과 동일하게 방문처리와 깊이 저장을 동시에 진행 (이건 토마토 배열 안에서 해도 될듯)
- 상하좌우 확인 0이면 1로 변경 후 큐에 넣기, 1이면 무시, -1이어도 무시
- 모든 토마토가 익었는지와 며칠이 걸렸는지는 배열을 돌며 확인
- 0인 부분이 있으면 -1출력
자료구조
- 토마토: int[][]
- Queue(BFS)
코드구현
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
tomato = [list(map(int,input().split())) for _ in range(m)]
cnt = 0
q = deque([])
# dfs 시작점 찾기
for i in range(m):
for j in range(n):
if tomato[i][j] == 1:
q.append((i,j))
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
#bfs시작
while q:
ey, ex = q.popleft()
for i in range(4):
ny = ey + dy[i]
nx = ex + dx[i]
if 0<=ny<m and 0<=nx<n: # 범위를 벗어나는지 확인
if tomato[ny][nx] == 0:
tomato[ny][nx] = tomato[ey][ex] + 1
q.append((ny, nx))
d = 0
# 방문하지 않은 곳이 있으면 -1 출력
# 가장 큰 깊이의 값을 찾음
for i in range(m):
for j in range(n):
if tomato[i][j] == 0:
print(-1)
exit()
d = max(tomato[i][j], d)
print(d-1)
마무리
- 골드 문제를 처음으로 원트에 성공했다.. ㅋㅋㅋㅋ
- 골드 4까지의 BFS문제는 다 풀 수 있을 것 같은 느낌이 들기 시작함
- 이젠 처음 문제를 어떻게 풀 것인가만 설계하는 단계를 좀 단축시키는게 필요할 것 같음
728x90
반응형
'코테준비 > 백준' 카테고리의 다른 글
[백준] 2502번: 떡 먹는 호랑이 - Python (0) | 2023.08.12 |
---|---|
[백준] 1629번: 곱셈 - Python (0) | 2023.08.07 |
[백준] 12851번: 숨바꼭질 2 - Python (0) | 2023.08.02 |
[백준] 1926번: 그림 - Python (0) | 2023.08.01 |