[BaekJoon] 7576 토마토

1.  문제 링크

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

2.  문제

요약

• 토마토를 격자 모양 상자의 칸에 하나씩 넣어서 보관하는데, 보관 후 하루가 지나면 익은 토마토들 인접한 곳에 있는 익지 않은 토마토들이 익은 토마토의 영향을 받아 익게 됩니다.
• 토마토의 인접한 곳은 상하좌우 네 방향에 있는 토마토를 의미합니다.
• 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지 최소 일수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 1,000보다 작거나 같은 상자의 가로 칸의 수 M, 상자의 세로 칸의 수 N이 주어지고 두 번째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어집니다.
  • 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타냅니다.
• 출력: 첫 번째 줄에 토마토 모두가 익을 때까지의 최소 날짜를 출력합니다. 만약 저장될 때부터 모든 토마토가 익어 있다면 0을 출력하고 토마토가 모두 익지 못하는 상황이면 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;

public class Main {
	static int[][] map;
	static Queue<Point> queue;
	public static int bfs() {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		while(!queue.isEmpty()) {
			Point cur_point = queue.poll();
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length) {
					if(map[cx][cy] == 0) {
						queue.offer(new Point(cx, cy));
						map[cx][cy] = map[cur_point.x][cur_point.y] + 1;
					}
				}
			}
		}
		int result = Integer.MIN_VALUE;
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[i].length; j++) {
				if(map[i][j] == 0) {
					return -1;
				}
				result = Math.max(result, map[i][j]);
			}
		}
		if(result == 1) {
			return 0;
		} else {
			return result - 1;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int col = Integer.parseInt(input[0]);
		int row = Integer.parseInt(input[1]);
		map = new int[row][col];
		queue = new LinkedList<Point>();
		for(int i = 0; i < row; i++) {
			input = br.readLine().split(" ");
			for(int j = 0; j < col; j++) {
				map[i][j] = Integer.parseInt(input[j]);
				if(map[i][j] == 1) {
					queue.offer(new Point(i, j));
				}
			}
		}
		br.close();
		bw.write(bfs() + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• 주어진 토마토들의 상태를 2차원 배열 map에 저장하고 입력받을 때 값이 1인 위치들을 Queue에 저장하여 BFS 수행 시에 사용합니다.
• Queue에 있는 위치들을 이용하여 각 위치의 상하좌우 위치를 확인하여 해당 위치가 map 안에 존재하고 해당 위치의 값이 0이라면, 즉 익지 않은 토마토라면 BFS를 통해 해당 위치의 상하좌우 위치도 확인하기 위해 해당 위치를 Queue에 넣고 지나간 일수를 표기하기 위해 해당 위치의 값을 (현재 위치의 값 + 1)로 변경합니다.

1. 주어진 크기의 2차원 배열 map을 생성하고 map에 주어진 토마토들의 상태를 저장하는데 만약 해당 값이 1이라면, 즉 익은 토마토라면 해당 위치를 BFS 수행 시에 사용할 Queue에 넣습니다.

2. BFS 알고리즘을 이용하여 토마토 모두가 익을 때까지의 최소 날짜를 구합니다.

   1. 상하좌우의 좌표에 해당하는 dx, dy 배열을 생성하고 값을 초기화합니다.

   2. Queue가 비워지기 전까지 반복문을 돌며 각각의 토마토가 익는 데에 걸리는 시간을 구합니다.

      1. Queue에서 현재 탐색하고자 하는 위치를 뽑아냅니다.
      2. 탐색하고자 하는 위치의 상하좌우 위치를 각각 확인하여 해당 위치가 map 안에 존재하고 해당 위치의 map 값이 0이라면, 즉 익지 않은 토마토라면 이후 BFS에서 해당 값을 탐색하기 위해 Queue에 해당 위치를 넣고 해당 토마토가 익는 시간을 나타내는 해당 위치의 map 값을 (탐색하고 있는 위치의 map 값 + 1)로 변경합니다.

   3. map 값 중 가장 큰 값, 즉 모든 토마토가 익는 데에 걸리는 시간을 나타내는 변수인 result를 생성하고 최소값으로 초기화합니다.

   4. map의 모든 위치를 돌면서 0이 존재한다면, 즉 아직 익지 않은 토마토가 존재한다면 모든 토마토가 익을 수 없는 상황이므로 -1을 출력합니다. 그렇지 않다면 result의 값을 원래 result의 값과 현재 위치의 map 값 중 큰 것으로 변경합니다.

   5. 만약 result 값이 1이라면 모든 토마토가 이미 익어있는 상태이므로 0을 출력합니다.

      • 이미 익지 않은 토마토가 존재하는 경우는 4번에서 확인하였기 때문에 해당 경우는 존재하지 않고 처음 익은 토마토의 값을 1이라고 하였으니 result가 1이라는 것은 시간이 지나지 않았음을 뜻하기 때문에 이미 모든 토마토가 익어있는 상태라고 할 수 있습니다.

   6. 그렇지 않다면 result 값을 출력합니다.