[인프런 자바/java] 12. 토마토(BFS 활용) _디버깅의 눈물

 

체크 포인트

 

1. BFS(너비 우선 탐색)를 이용하는 문제

-토마토가 모두 익을 때까지 '최소 일자'를 구하는 문제이기 때문에, 최단 경로를 구하는 BFS로 접근

 

2. 다수의 (x,y)를 큐에 넣어주는 부분

6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1

-이 문제에서는 bfs 탐색을 시작할 때, 익은 토마토(1)를 기준으로 탐색을 시작한다. 예시 문제에서는 (1,2)와 (3,5)가 익은 상자 내 토마토가 존재하는 위치이다.

 

// Q 선언
static Queue<Integer[]> Q = new LinkedList<Integer[]>();
// 좌표 추가하는 방식
Q.add(new Integer[]{i,j});

-다수의 x값과 y값(x,y)을 큐에 넣어주기 위해서 위와 같이 Integer배열 타입으로 선언해 처히했다.

 

3.시작 시 익은 토마토를 단계별로 탐색해나가야 한다.

-1단계 : (1,2), (3,5) 탐색

-2단계 : (1,1), (1,3), (3,4) 탐색

...

위와 같이 단계별로 bfs 탐색을 처리하기 위해서는

1)우선 1단계 시작점들((1,2), (3,5))을 큐에 넣어주고,

 

		// bfs 탐색 시작
		bfs();

 

2)위와 같이 단계별 진행하도록 처리하였다.

 

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	// 상자 가로 칸의 수 M, 세로 칸의 수 N
	static int M, N;
	
	// 상자 배열
	static int[][] map;
	
	// bfs 탐색 시 상,하,좌,우 이동 좌표
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	
	static Queue<Integer[]> Q;
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine(), " ");
		
		// 상자 가로 칸의 수
		M = Integer.parseInt(st.nextToken());
		// 상자 세로 칸의 수
		N = Integer.parseInt(st.nextToken());
		
		// 상자 배열 초기화
		map = new int[N][M];
		
		// 상자 내 토마토 정보 입력
		for(int i=0; i<N; i++){
			
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int j=0; j<M; j++){
				
				map[i][j] = Integer.parseInt(st.nextToken());
				
			}
		}

		// 큐 초기화
		Q = new LinkedList<Integer[]>();
		
		// 이미 모든 토마토가 익어있는 상태인지 확인하는 변수
		int zeroCheck = 0;
		
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				// 시작 시 익은 토마토를 모두 큐에 넣어준다.
				// bfs 1단계 시 탐색을 시작할 토마토 위치
				if(map[i][j]==1){
					Q.add(new Integer[]{i,j});
				}
				// 안 익은 토마토가 있는 경우,
				if(map[i][j]==0){
					zeroCheck++;
				}
			}
		}
		
		// 시작 지점에서 모든 토마토가 이미 익은 상태라면,
		if(zeroCheck==0){
			System.out.println("0");
			return;
		}
		
		// bfs 탐색 시작
		bfs();
		
		// 모든 토마토가 익기 까지의 최대 일수
		int max = Integer.MIN_VALUE;
		// 토마토가 익을 수 없는 경우,
		int cannnotCheck = 0;
		
		for(int i=0; i<N; i++){
			for(int j=0; j<M; j++){
				if(max<map[i][j]){
					// 모든 토마토가 익을 때까지의 최대 일수
					max = map[i][j];
				}
				// 토마토가 익을 수 없는 경우,
				if(map[i][j]==0){
					cannnotCheck++;
				}
			}
		}
		
		// 모든 토마토가 익었다면,
		if(cannnotCheck==0){
			System.out.println(max-1);
		}
		// 익지 못한 토마토가 존재한다면,
		else{
			System.out.println("-1");
		}
		
	}
	
	
	public static void bfs(){
		
		while(!Q.isEmpty()){
			
			Integer[] arr = Q.poll();
			
			int tempX = arr[0];
			int tempY = arr[1];
			
			// 주어진 (tempX, tempY)로부터 상,하,좌,우 탐색
			for(int i=0; i<4; i++){
				
				int nx = tempX + dx[i];
				int ny = tempY + dy[i];
				
				// 새로운 x(nx), 새로운 y(ny)가 상자 내에 존재한다면,
				if(nx>=0 && ny>=0 && nx<N && ny<M){

					// 방문하지 않았던 위치라면 탐색
					if(map[nx][ny]==0){
						Q.add(new Integer[]{nx,ny});
						// 새로운 (nx,ny)를 방문처리 및
						// 해당 map[nx][ny]값을 날짜로 +1 처리
						map[nx][ny] = map[tempX][tempY] + 1;
					}
				}
			}
		}
		
	} // end of bfs
	
	
}