[BOJ - JAVA] 7576 - 토마토(BFS)

# 주소

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

7576번: 토마토

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.Point;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static int[] dx = {1,0,0,-1};
	public static int[] dy = {0,1,-1,0};
	public static int width,height, start_x,start_y;
	public static int count;
	public static boolean visit[][];
	public static int arr[][];
	public static ArrayList<Integer> list = new ArrayList<>();
	public static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	height = scan.nextInt();
    	width = scan.nextInt();
    	arr = new int[width][height];
    	count = 0;
    	for(int i = 0; i < width; i++) {
    		for(int j = 0; j < height; j++) {
    			arr[i][j] = scan.nextInt();
    			if(arr[i][j] == 1) {
    				queue.offer(new Point(i,j));
    			}
    		}
    	}
    	System.out.println(bfs());
    }
    public static int bfs() {
    	while(!queue.isEmpty()) {
    		Point now = queue.poll();
    		int x = now.x;
    		int y = now.y;
    		for(int i = 0; i < 4; i++) {
    			int nx = x + dx[i];
    			int ny = y + dy[i];
    			if(nx >= 0 && ny >= 0 && nx < width && ny < height) {
    				if(arr[nx][ny] == 0) {
    					queue.add(new Point(nx,ny));
    					arr[nx][ny] = arr[x][y] + 1;
    				}
    			}
    		}
    	}
    	for(int i = 0; i < width; i++) {
    		for(int j = 0; j < height; j++) {
    			if(arr[i][j] == 0) {
    				return -1;
    			}
				count = Math.max(count, arr[i][j]);
    		}
    	}
    	if(count == 1)
    		return 0;
    	else
    		return count - 1;
    }
}

이번에도 BFS문제를 가져왔습니다.

입력문을 쭉 읽고 음 BFS인가 해서 위에지문을 읽어보니 처음엔 무슨 의민지 파악이 안됐었습니다.

계속 읽어보니, 1이 적혀있는 위치에서 시간이 지날수록 주변 토마토가 익어가고 있으므로 이것은 BFS문제라는 것을 이해했습니다. 또한, 상하좌우 총 네방향으로만 움직일 수 있으므로 public static int[] dx,dy 는 각 각 4개의 값을 가져야 합니다.

 

제일 처음 입력받는 height와 width는 입력받을 배열의 행과 열입니다.

예제에서는 6 4가 입력되었으므로 arr의 크기는 arr[4][6]이 됩니다.

그리고 count = 0인데, 이 count가 나중에 토마토가 모두 익는 날짜여서 처음엔 0으로 시작합니다.

그리고 arr를 입력받아야 하므로 scan.nextInt()를 이용하여 arr를 입력받은 후 arr[i][j]의 위치가 bfs의 시작점이므로 arr값이 1인 지점을 Point에 담아, queue에 담습니다.(이것이 제일 핵심)

그리고 bfs문을 짜겠습니다.

while(!queue.isEmpty())는 queue를 다룰 때 필수입니다. while문 안으로 들어가서, 현재 위치의 Point의 점을 queue.poll()하여 가져옵니다. 그리고 그 때의 x,y를 가져온 후 for문에서 nx와 ny를 nx = x+dx[i], ny = y + dy[i]로 정의하는데 nx와 ny는 1을 기준으로 이동하게 될 위치입니다. 아까 말했듯이 움직이는건 상하좌우로 총 4방향으로만 움직일 수 있기 대문에 for문에서 i는 4까지만 이동가능하구요. 이 때 이중 if문을 쓸 텐데, nx,ny가 모두 0보다 크거나 같고 배열의 width,height 보다 작아야 한다는 조건을 거셔야 합니다. 그리고 arr가 만약 0이라면 방문하지 않은 값이기 때문에 (-1이 여기서 벽이므로 무시하고 0인 지점만) queue에 담고 그 nx,ny값을 기존 x,y에서 1씩 더합니다. 이것을 queue에 담을텐데, 여기서 꼭 알아야 할 것이 있습니다.

queue는 선입선출(FIFO)구조이기 때문에 지금 삽입된, 이동한 점의 위치는 가장 마지막에 빠져나옵니다. 즉, 아까전에 제일 윗부분에 arr가 1이면 queue에 점을 삽입했었던거 기억나시죠???

그 부분에서 만약 arr가 1인 점이 3개라고 가정해봅시다. 예를들면 (1,1), (2,3), (4,5) 이런식으로요.

그럼 1인 점이 3개이니까 queue에는 언급한 점 3개가 담기게 됩니다. 이 점들은 각각 그 위치에서 bfs가 실행될테고 (1,1)주변이 전부 0이라면 (1,2), (2,1)이 모두 2가되고 queue에 담깁니다. 이 때! queue를 조회해보면 (2,3), (4,5), (1,2), (2,1)이 될 것이고 다음으로 실행되는 queue문은 새로 넣은 (1,2), (2,1)이 아닌, (2,3)이 실행된다는 뜻입니다. 이 문제의 핵심은 bfs? 좋습니다 근데 이 bfs의 영역을 단순히 구하는 것이 아니라, 동시다발적으로 bfs가 일어날 때 이 배열을 모두 0이 아닌 값으로 만드는데 필요한 최소한의 길이를 물어보는 문제입니다. 따라서 반드시 queue가 필요한 것이구요. 이해되셨나요???

그럼 이 bfs를 쭉 시행하면 분명 모든 arr들이 -1이 아니라면 1보다 크거나 같은 수들로 이루어져 있을 것입니다. 이 때 가장 큰 arr값을 Math.max를 이용하여 count에 담은 후 그것을 return해주면 정답이 되는 것입니다. 단, arr가 0이될 경우에는 -1이라는 벽 때문에 지나가질 못하는 것이므로 return -1을 해주시고 count가 1이 될 때도 -1을 출력해주셔야 원하는 정답을 얻으실 수 있습니다.

감사합니다.