자바(Java) 알고리즘 문제 풀이 - 토마토(BFS 활용)

문제 이해

- 토마토들이 모두 익는데 걸리는 최소일수를 구하라.

 

해결 전략

- 큐에 board[x][y] = 1인 점들을 넣습니다.

- 큐에서 값을 하나씩 제거하면서, 인접한 위치의 점이 

   (1) board 내부에 있고 

   (2) board[x][y]=0 

   이라면 해당 위치에 일수를 기록합니다.  

- dis배열에 기록된 값 중 최대값을 반환합니다. 

 

구현

import java.util.*;
class Point{
	public int x, y;
	Point(int x, int y){
		this.x=x;
		this.y=y;
	}
}

public class Main {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	static int n, m;
	static Queue<Point> Q=new LinkedList<>();
	public void BFS(){
	    
	    
	    while(!Q.isEmpty()){
	        
	        Point cur = Q.poll();
	        
	        for(int i=0; i<4; i++){
	            int nx = cur.x+dx[i];
	            int ny = cur.y+dy[i];
	            
	            if(0<=nx && nx<n && 0<=ny && ny<m && board[nx][ny] == 0){
	                board[nx][ny] = 1;
	                dis[nx][ny] = dis[cur.x][cur.y] + 1;
	                Q.offer(new Point(nx, ny));
	            }
	        }
	       
	    }
	
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		m=kb.nextInt();
		n=kb.nextInt();
		board=new int[n][m];
		dis=new int[n][m];
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				board[i][j]=kb.nextInt();
				if(board[i][j]==1) Q.offer(new Point(i, j));
			}
		}
		T.BFS();
		boolean flag=true;
		int answer=Integer.MIN_VALUE;
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(board[i][j]==0) flag=false;
			}
		}
		if(flag){
			for(int i=0; i<n; i++){
				for(int j=0; j<m; j++){
					answer=Math.max(answer, dis[i][j]);
				}
			}
			System.out.println(answer);
		}
		else System.out.println(-1);
	}
}

 

피드백

- 처음 시작 위치는 이미 board[x][y] = 1이기 때문에 따로 처리할 필요가 없습니다.