[BEAKJOON] 7576번 토마토

---

1(익은 토마토)인 위치에서 하루가 지날 때마다 맞닿은 부분(0)이 1로 변경된다.

내 주변 탐색 후 변경하는 과정을 반복해야 한다.

너비우선탐색 문제 유형으로 큐에 삽입하여 과정을 하나씩 따라가본다.

 

1(익은 토마토)의 위치가 여러 개일 경우는?

큐에 전부 넣어서 해결한다.

하루가 지날 때마다 큐에 저장된 모든 경로를 따라가 0을 1로 바꾼다!

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

public class Main {
	static int N, M;
	static int dx[] = {1,-1,0,0};
	static int dy[] = {0,0,1,-1};
	static String arr[][];
	static Queue<Point> queue = new LinkedList<>();
	static int cnt = 0, days = 0;
	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());
		arr = new String[N][M];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				String new_one = st.nextToken();
				arr[i][j] = new_one;
				if(new_one.equals("1")) {
					queue.add(new Point(i,j));
				}else if(new_one.equals("0")) // 익혀야 하는 토마토 개수
					cnt++;
			}			
		}
		bfs();
		System.out.println((cnt==0)? days:-1); // 큐가 비어서 탐색이 끝났는데도 토마토가 남았다면 임무 실패 ㅜ.ㅜ
	}
	
	static void bfs() {
		while(cnt>0 && !queue.isEmpty()) { // 익혀야 하는 토마토가 남았고, 큐에도 갈 수 있는 경로가 남아있을 경우
			for(int s = queue.size(); s>0; s--) { // 하루에 익힐 수 있는 토마토 위치 모두 방문
				Point current = queue.poll();	  // 현재 토마토가 있는 위치 꺼내서
				
				int current_x = current.x;
				int current_y = current.y;
				
				for(int i=0; i<4; i++) {		  // 익힐 수 있는 토마토 탐색
					int new_x = current_x+dx[i];
					int new_y = current_y+dy[i];
					
                    // 익힐 수 있는 토마토 발견했다면 방문 표시
					if(new_x>=0 && new_x<N && new_y>=0 && new_y<M && arr[new_x][new_y].equals("0")) {
						queue.add(new Point(new_x, new_y));
						arr[new_x][new_y] = "1";
						cnt--; // 이 토마토는 익혔습니다!
					}
				}
			}
            // 오늘 익힐 수 있는 토마토 처리 완료!
			days++;
			
		}
	}

	static class Point{
		int x,y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

[출처]

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

7569번: 토마토