백준 7576 토마토

문제

---

7576번: 토마토 (acmicpc.net)

해결방법

---

• BFS를 사용하면 되는 문제다. 2차원 배열을 입력받으며 익은 토마토를 모두 큐에 입력해놓고 BFS 진행하면 된다.

• BFS 반복문에서 마지막에 day 값을 더해주기 때문에 -1 부터 시작해야 한다.

• BFS 반복문을 통해 익힐 수 없는 토마토가 존재 할 수 있기 때문에 마지막에 배열을 순회하며 찾아봐야한다.

동작과정

---

1. 입력을 받으며 익은 토마토의 위치를 저장한다.
2. 익은 토마토들이 들어있는 큐를 통해 다음 익힐 토마토를 찾아서 map의 값을 변경해주고 큐에 위치를 추가한다.
3. 반복문이 진행될 때 마다 day 값을 증가시킨다.
4. 반복문 종료 후 익히지 못한 남은 토마토가 있는지 찾는다. 있다면 day 값을 -1로 변경해준다.

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/*
 * BFS를 통한 2차원 배열을 탐색하는 구현문제
 */
public class Main {
	
	private static class Point {
		int y;
		int x;

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

	}
	
	private final static int[][] D = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
	private static int N, M;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(in.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N][M];
		
		Queue<Point> q = new ArrayDeque<>();
		
		// 맵을 입력받으며 해당 위치에 익은 토마토가 있다면 q에 추가한다.
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1)
					q.add(new Point(i, j));
			}
		}
		
		// day는 -1부터 시작, 더이상 새로운 토마토를 익게 할 수 없을 때 까지 실행함
		int day = -1;
		while(!q.isEmpty()) {
			
			// 현재 큐에 들어있는 토마토 만큼 실행
			int size = q.size();
			while(size-- > 0) {
				Point tomato = q.poll();
				
				// 4방향 탐색하여 해당 위치에 익지 않은 토마토가 있다면 해당 위치를 큐에 추가하고 토마토를 익었다고 맵에 표시함
				for(int d = 0; d < 4; d++) {
					int dy = tomato.y + D[d][0];
					int dx = tomato.x + D[d][1];
					
					if(isInBound(dy, dx) && map[dy][dx] == 0) {
						map[dy][dx] = 1;
						q.offer(new Point(dy, dx));
					}
				}
			}
			
			// 다음 날
			day++;
		}
		
		// 맵을 순회하며 익지않은 토마토가 있다면 day를 -1로 설정함
		external:
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] == 0) {
					day = -1;
					break external;
				}
			}
		}

		out.write(day + "");
		out.flush();
	}
	
	// 범위 체크
	private static boolean isInBound(int y, int x) {
		return y >= 0 && y < N && x >= 0 && x < M;
	}
}