[백준/자바] 7576 : 토마토

 

https://www.acmicpc.net/problem/7576

7576번: 토마토

---

BFS를 활용한 최소비용 문제이다.

간단한 BFS 문제라고 생각했지만 익은 토마토가 여러 개일 경우,

각 위치에서 하루마다 익는 토마토를 어떻게 처리해야할 지 고민했다.

이를 포함해서 문제를 풀면서 고려한 부분은 총 3가지 이다.

 

1. 익은 토마토가 여러 개일 경우 하루마다 익는 토마토 처리 방식

   

처음에는 토마토가 익을 때마다 count를 증가시키는 방식으로 생각했지만,

하루에 여러 곳에서 익는 토마토를 처리해주지 못했다.

 

따라서 다음 위치에 이전 위치 값 + 1을 해주는 형식으로 수정해 여러 토마토에서 접근해와도

같은 결과를 가질 수 있도록 바꿔주었다.

 

즉, BFS는 너비탐색이므로 depth 1을 모두 처리한 후 depth 2로 넘어가므로

다음 depth로 넘어갈 때 현재 depth에서 1을 증가시켜주는 방식이다.

tomato[nx][ny] = tomato[x][y] + 1;

 

2. 토마토가 모두 익지 못하는 상황 식별

 

토마토가 없는 칸으로 인해 존재하는 토마토가 모두 익지 못하는 상황을 식별하기 위해

토마토 개수를 구해 처리하였다.

+) 반복문을 통해 2차원 배열 내 0의 개수를 구하는 방식도 가능하다.

 

3. 처음부터 토마토가 다 익어있는 상황 식별

 

토마토 값이 1부터 시작하므로 최소 일수값 -1 처리를 해주어야 한다.

하지만 처음부터 토마토가 다 익어있는 경우 -1 처리를 해주지 않아도 되므로

이를 처리하기 위한 조건문을 추가하였다.

 

최종 코드는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {

	static LinkedList<Integer[]> que;
	static int[][] tomato;
	static int M, N, tomato_count;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken()); // 열
		N = Integer.parseInt(st.nextToken()); // 행

		tomato = new int[N][M];
		que = new LinkedList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int t = Integer.parseInt(st.nextToken());
				tomato[i][j] = t;

				if (t == 1) {
					que.addLast(new Integer[] {i, j});
				} else if(t == 0) {
					tomato_count += 1;
				}
			}
		}
		
		int[] ans = bfs();
		
		if(ans[1] == tomato_count) {
			if(ans[0] == 0) System.out.println(ans[0]);
			else System.out.println(ans[0]-1);
		}else {
			System.out.println(-1);
		}
		
	}

	public static int[] bfs() {
		int[] dx = { 1, -1, 0, 0 };
		int[] dy = { 0, 0, 1, -1 };
		int count = 0;
		int shortest = 0;
		
		while (!que.isEmpty()) {
			Integer[] point = que.removeFirst();

			for (int i = 0; i < 4; i++) {
				int nx = point[0] + dx[i];
				int ny = point[1] + dy[i];
				if(nx >= 0 && nx < N && ny >= 0 && ny < M && tomato[nx][ny] == 0) {
					tomato[nx][ny] = tomato[point[0]][point[1]] + 1;
					que.addLast(new Integer[] {nx, ny});
					shortest = tomato[nx][ny];
					count += 1;
				}
			}
		}
		
		return new int[] {shortest, count};
	}

}

 

BFS를 활용한 최소비용을 구할 때 이전값 + 1 하는 방식 사용!