bj_7576. 토마토

bj_7576. 토마토

- 문제 링크 : https://www.acmicpc.net/problem/7569

1. 문제 이해

- 상자의 크기 = M x N

- 보관 후 하루가 지날 때마다 익은 토마토의 상하좌우에 인접한 안 익은 토마토는 익는다.

- 상자에 비어 있는 곳이 존재한다.

- 익은 토마토 = 1, 안 익은 토마토 = 0, 빈 곳 = -1

- 저장할 때부터 토마토가 모두 익어있으면 0, 토마토가 모두 익지 못하는 상황이면 -1 출력

→ 결론 : 토마토가 모두 익는데 걸리는 최소 일수 구하기

2. 풀이 방법

- 상자의 가로가 M, 세로가 N이기 때문에 행이 N이고, 열이 M이다. 둘의 값을 반대로 사용하지 않도록 유의한다.

- 익은 모든 토마토가 동시 에 주변 토마토를 익게 만들어야 하며, 그중 최소 일수 를 구해야 하기 때문에 BFS를 이용한다.

- 빈 곳은 토마토를 익히기 전에 방문을 이미 완료한 곳으로 설정하고 시작한다.

- 빈 곳과 상자로 둘러싸인 토마토는 절대 익을 수 없다. 이런 경우를 확인하기 위해 방문한 곳들을 카운트하여 모두 익지 못하는 상황인지 확인한다. 또한 저장할 때부터 모두 익은 토마토 인지도 확인이 가능하다. 전체를 방문하게 되면 카운트 수는 MxN이다.

3. 소스 코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int M; // 상자 가로 static int N; // 상자 세로 static int[][] box; // 토마토 상자 static boolean[][] visited; // 익은 정도 확인 static List list; // 익은 토마토 위치 저장 static int cnt; // 방문한 개수 static int time; // 소요된 일수 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st = null; public static void main(String[] args) throws IOException { // 토마토 st = new StringTokenizer(br.readLine(), " "); M = Integer.parseInt(st.nextToken()); N = Integer.parseInt(st.nextToken()); box = new int[N][M]; visited = new boolean[N][M]; list = new ArrayList<>(); for(int r=0; r queue = new LinkedList<>(); // 익은 토마토는 큐에 모두 넣고 시작 for(int t=0; t0) { Tomato head = queue.poll(); for(int d=0; d=0 && r=0 && c

4. 실행 결과

5. 리뷰

- '최소'라는 키워드를 통해 BFS와 관련된 문제라는 것을 파악할 수 있어서 비교적 쉽게 해결한 문제였다.

- 상자의 크기가 M N으로 주어져 처음에 배열의 크기를 반대로 설정하여 입력값을 잘못받았었다. 익숙함에 속지 말자.

from http://45jung.tistory.com/22 by ccl(A) rewrite - 2021-09-24 16:27:16