Search

BOJ 7576 토마토

태그
그래프 이론
그래프 탐색
너비 우선 탐색
생성일
2024/12/11 12:13

문제 설명

•
토마토가 모두 익을 때까지의 최소 날짜를 구하는 문제
◦
단, 토마토가 모두 익을 수 없을 경우 -1을 출력

예제 입력/출력

•
입력1
6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Plain Text
복사
•
출력1
8
Plain Text
복사

제약 조건

•
2≤M,N≤1,0002 ≤ M, N ≤ 1,000
◦
MM: 가로의 크기
◦
NN: 세로의 크기

문제 풀이

•
그래프 탐색을 이용하여 문제를 해결하면 된다. - O(NM)O(NM)
◦
노드의 최대 개수가 NMNM이고, 나올 수 있는 간선의 최대 개수는 4NM4NM
▪
최악의 경우 O(NM+4NM)O(NM + 4NM)
◦
BFS 알고리즘을 이용

풀이 코드

풀이1
풀이1 코드 개선