BFS를 활용한 '토마토 농장' 문제 해결: 최단 시간 탐색 전략

📅 2025-08-17T07:03:14.436567 👤 긍긍 🏷️ 개발

완성도:

0.9

🤖 AI 추천

이 콘텐츠는 알고리즘 학습에 대한 열정이 있는 모든 개발자에게 추천됩니다. 특히 그래프 탐색 알고리즘, 그중에서도 BFS의 원리와 실제 코딩 문제 적용에 대해 배우고 싶은 주니어 개발자나 컴퓨터 공학 전공 학생에게 매우 유익할 것입니다. BFS를 활용한 최단 거리 문제 해결 능력을 키우고 싶은 개발자라면 누구나 큰 도움을 받을 수 있습니다.

🔖 주요 키워드

BFS 너비 우선 탐색 그래프 탐색 최단 거리 알고리즘 자료구조 코딩 테스트 백준 7576 토마토

핵심 기술

본 콘텐츠는 BFS(너비 우선 탐색) 알고리즘을 사용하여 '토마토 농장' 문제(BOJ 7576)의 최소 일수(최단 거리)를 해결하는 방법을 설명합니다. BFS의 레벨 단위 탐색 특성을 활용하여 익은 토마토가 전파되는 과정을 시뮬레이션하는 것이 핵심입니다.

기술적 세부사항

문제 분석: '토마토 농장' 문제는 익은 토마토가 인접한 익지 않은 토마토를 익게 만드는 과정을 통해 모든 토마토가 익는 데 걸리는 최소 일수를 구하는 문제입니다.
BFS 적용 이유:
- 최소 일수 = 최단 거리 문제로, BFS가 가장 적합합니다.
- BFS는 큐를 사용하여 레벨(단계)별로 탐색하므로, 하루에 익는 토마토들을 동시에 처리하는 데 유리합니다.
- DFS는 시간 개념을 제대로 표현하기 어렵습니다.
BFS 기본 로직: 큐를 사용하여 시작 노드를 방문 처리하고 큐에 삽입합니다. 큐가 빌 때까지 반복하며 노드를 꺼내고, 인접 노드 중 방문하지 않은 노드를 방문 처리 후 큐에 추가합니다.
토마토 문제 해결 로직:
- 초기 익은 토마토(1)를 모두 큐에 넣고, 각 토마토의 익은 날짜(0)를 함께 저장합니다 (new int[]{i, j, 0}).
- BFS 탐색 중 가장 마지막에 익은 토마토의 날짜(day)를 maxDays 변수에 저장하여 전체 최단 일수를 추적합니다.
- 상하좌우 인접 칸(ni, nj)을 탐색하며, 유효한 범위 내이고 익지 않은 토마토(arr[ni][nj] == 0)인 경우, 해당 토마토를 익게 만들고(arr[ni][nj] = 1), 다음 날짜(day + 1)와 함께 큐에 추가합니다.
- BFS 완료 후, 익지 않은 토마토(0)가 남아있다면 -1을, 그렇지 않다면 maxDays를 반환합니다.