[BOJ] 7576 토마토

7576번: 토마토 (acmicpc.net)

계속해서 BFS 문제를 풀다보니 이제 어느 정도 익숙해진 것 같다.
이번 문제는 기존 BFS에서 level을 증가시키기 위해 단계별로 depth를 구했다.

그냥 BFS와의 차이점은 큐의 사이즈를 구해서 현재depth에서 for문을 이용해 같은 Depth에 있는 모든 노드를 방문하는 것이다.
여기서 주의해야하는 점은 queue의 사이즈가 변하기 때문에 단순히 for(int a = 0; a <q.size(); a++) 이런식으로 하면 안된다.
미리 q.size를 변수로 받아오고, 이를 기준으로 for문을 돌려야 한다.

문제를 처음 풀었을 때는 마지막에 안익은 토마토가 있는지 확인하기 위해, 2차원배열 map의 모든 좌표를 탐색하면서 0이 있는경우 break(탈출)하는 식으로 풀었다.
속도가 좀 느린것 같아서, 접근 방식을 바꾸었는데, 처음부터 덜익은 토마토의 개수를 세고, DFS를 하면서 덜익은 토마토의 개수를 감소시키는 방식으로 바꾸었다.

이렇게 하면 BFS가 끝났을 때, 안익은 토마토가 없다면 덜익은 토마토 개수를 저장하는 변수(nr)의 값이 0이 될 것이다.

package _04._0413;

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

public class BOJ7576Tomato {
	static class Pos{//좌표 정보 저장을 위한 클래
		int x;
		int y;
		
		public Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}

	private static int[] dx = {1,0,-1,0};
	private static int[] dy = {0,-1,0,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int C = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int[][] map = new int[R][C];
		List<Pos> ripe = new ArrayList<>();//익은 토마토의 좌표를 저장할 리스트
		int nr =0; // 덜익은 토마토 개수
		int rcnt=0; //for문을 돌리기 위해서 익은 토마토 개수저장
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				int tomato = Integer.parseInt(st.nextToken());
				map[i][j] = tomato; //map에 토마토 정보를 저장
				if(tomato==1) {
					ripe.add(new Pos(i,j)); //익은 토마토 정보 저장 
					rcnt++; //익은 토마토 개수 증가
				}else if(tomato==0) {
					nr++; //익어야 하는 토마토 수 증가
				}
			}
		}//input
		int level=-1; //시작하자마자 레벨이 증가하므로 
		Queue<Pos> q = new LinkedList<>();
		for (int i = 0; i < rcnt; i++) {
			q.offer(ripe.get(i));
		}
		while (!q.isEmpty()) {
			int size = q.size(); //같은 단계에 있는 익은 토마토를 처리하기 위해 for문으로 묶었다.
			for (int i = size; i >0; i--) {
				Pos temp = q.poll();
				int px = temp.x;
				int py = temp.y;
				for (int d = 0; d < 4; d++) {//4방 탐색
					int nx = px+dx[d]; //dx dy를 이용하여 4방의 좌표 계산
					int ny = py+dy[d];
					if(nx<0 || ny<0 || nx>=R || ny>=C) continue; //범위를 벗어나는 경우
					if( map[nx][ny]!=0)continue;//토마토가 이미 익거나, 없는경우
					map[nx][ny] = 1;
					nr--; //익어야 하는 토마토 개수를 감소 
					q.offer(new Pos(nx,ny));
				}
			}
			level++; //for문이 1번 끝나면 레벨이 증가 
		}
		System.out.print(nr==0?level :-1); //덜익은 토마토 개수가 0개이면 레벨을 출력 
		//덜익은 토마토가 있으면 -1 출력 
	}//main
}