[Java] 백준 7576번 : 토마토

1. 문제

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

7576번: 토마토

 

 

2. 풀이 과정

- bfs

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] map = new int[M][N];
		Queue<int[]> tomato = new LinkedList<>();//토마토 위치
		
		//입력
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
					tomato.offer(new int[] {i, j});
				}
			}
		}
		
		//토마토 익기
		int day = 0;
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		while(!tomato.isEmpty()) {
			boolean isChange = false;
			for(int i=0, s = tomato.size(); i<s; i++) {
				int[] pos = tomato.poll();
				for(int j=0;j<4;j++) {
					int nx = pos[0] + dx[j];
					int ny = pos[1] + dy[j];
					if(0<=nx && nx<M && 0<=ny && ny<N && map[nx][ny] == 0) {
						isChange = true;
						map[nx][ny] = 1;
						tomato.offer(new int[] {nx, ny});
					}
				}
			}
			if(isChange)
				day++;
		}
		// 안익은 토마토 있는지 확인
		for(int i=0; i<M; i++) {
			for(int j=0; j<N;j++) {
				if(map[i][j] == 0) {
					day = -1;
					break;
				}
			}
		}
		System.out.println(day);
	}

}

 

결과