12. 토마토(BFS 활용)

 

설명

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.

 

 

 

 

예시

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

 

4

 

 

 

 

풀이

1. 이중 for문을 탈출 하는 방법

Loop1: 이렇게 써주고 탈출하고 싶을때 break Loop1;해준다.

 

하지만 굳이 이렇게 안하고 그냥 밑에 if(flag) else~ 이런식으로 판단해줘도 된다.

 

2. 

큐에 넣고 좀비처럼 꺼내가지고 board 체크하면서 dis배열에다가 거리 1씩증가시키면서 넣기...

 

 

import java.util.*;

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

class Main {

	static int[] dx= {-1,1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n;
	static int m;
	static int [][] board;
	static int [][] dis;
	static Queue<Point> queue= new LinkedList<>();
	public void BFS(int[][]board) {
		

		
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				
			}
		}
		while(!queue.isEmpty()) {
			Point tmp = queue.poll();
			for(int i=0; i<4; i++) {
				int nx= tmp.x+dx[i];
				int ny= tmp.y+dy[i];
				
				
				if(nx>=0 && ny>=0 && nx<m && ny<n && board[nx][ny]==0) {
					board[nx][ny]=1;
					dis[nx][ny]=dis[tmp.x][tmp.y]+1;
					queue.add(new Point(nx,ny));
				}
			}
		}
		
		boolean flag=true;
		int max= Integer.MIN_VALUE;
		
		for(int i=0; i<m ;i++) {
			for(int j=0; j<n; j++) {
				if(board[i][j]==0) {
					flag=false;
				}
			}
		}
		if(flag) {
			for(int i=0; i<m ;i++) {
				for(int j=0; j<n; j++) {
					if(dis[i][j]>max) {
						max=dis[i][j];
					}
				}
			}
		}
		if(flag) {
			System.out.println(max);
		}else {
			System.out.println(-1);
		}

		
	}
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		
		n= sc.nextInt();
		m= sc.nextInt();
		
		board= new int[m][n];
		dis= new int [m][n];
		
		for(int i=0; i<m ;i++) {
			for(int j=0; j<n; j++) {
				board[i][j]=sc.nextInt();
				if(board[i][j]==1) {
					queue.add(new Point(i,j));
				}
			}
		}
		
		T.BFS(board);
		

	}

	
}

import java.util.*;

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

class Main {

	static int[] dx= {-1,1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n;
	static int m;
	static int [][] board;
	static int [][] dis;

	public void BFS(int[][]board) {
		
		Queue<Point> queue= new LinkedList<>();
		
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				if(board[i][j]==1) {
					queue.add(new Point(i,j));
				}
			}
		}
		while(!queue.isEmpty()) {
			Point tmp = queue.poll();
			for(int i=0; i<4; i++) {
				int nx= tmp.x+dx[i];
				int ny= tmp.y+dy[i];
				
				
				if(nx>=0 && ny>=0 && nx<m && ny<n && board[nx][ny]==0) {
					board[nx][ny]=1;
					dis[nx][ny]=dis[tmp.x][tmp.y]+1;
					queue.add(new Point(nx,ny));
				}
			}
		}
		
		boolean flag=true;
		int max= Integer.MIN_VALUE;
		
		Loop1:
		for(int i=0; i<m ;i++) {
			for(int j=0; j<n; j++) {
				if(board[i][j]==0) {
					System.out.println("-1");
					flag=false;
					break Loop1;
				}
			}
		}
		if(flag) {
			for(int i=0; i<m ;i++) {
				for(int j=0; j<n; j++) {
					if(dis[i][j]>max) {
						max=dis[i][j];
					}
				}
			}
		}
		if(flag) {
			System.out.println(max);
		}

		
	}
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		
		n= sc.nextInt();
		m= sc.nextInt();
		
		board= new int[m][n];
		dis= new int [m][n];
		
		for(int i=0; i<m ;i++) {
			for(int j=0; j<n; j++) {
				board[i][j]=sc.nextInt();
			}
		}
		
		T.BFS(board);
		

	}

	
}