[ Baekjoon ] #7576 토마토

[Baekjoon][https://www.acmicpc.net/problem/7576]

 

- 너비 우선 탐색(BFS) 알고리즘

 

정수 1은 익은 토마토로 하루가 지나면 상, 하, 좌, 우로 인접한 익지 않은 토마토에게 영향을 준다. 출력해야할 답은 보관된 토마토들이 몇일이 지나면 다 익게 되는지 최소 일수를 구하는 문제로 너비 우선 탐색(BFS) 알고리즘을 적용했다.

 

창고 Map[n][m] 을 입력하면서 Queue에 현재 익은 토마토의 위치를 저장 후 BFS 알고리즘을 호출한다.

Queue에 값이 존재 하지 않을 때까지 인접한 익지 않은 토마토(map[n][m] ==0) && 방문하지 않은 좌표(visit[n][m] == 0) 에 방문하여 익지 않은 토마토를 익은 토마토로 값을 변경하여 저장.

 

이후 Queue에 더 이상 값이 존재 하지 않을 때의 날짜를 출력한다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class TomatoLocation{
	int x;
	int y;
	
	public TomatoLocation(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

public class Main {

	static int m;
	static int n;
	static int[][] map;
	static int[][] visit;
	static Queue<TomatoLocation> t;
	static int result_cnt = -1;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		
		m = sc.nextInt(); // 가로
		n = sc.nextInt(); // 높이
		
		map = new int[n][m];
		visit = new int[n][m];
		t = new LinkedList<TomatoLocation>();
		
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				map[i][j] = sc.nextInt();
				if(map[i][j] == 1 && visit[i][j] == 0) {
					t.offer(new TomatoLocation(i, j));
				}
			}
		}
		
		getBFS();
		
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map[i][j] == 0)
				{
					result_cnt = -1;
				}
			}
		}
		
		System.out.println(result_cnt);
	}
	
	public static void getBFS()
	{
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0 ,-1};
		
		while(!t.isEmpty())
		{
			int tomato_size = t.size();		
			for(int i=0;i<tomato_size;i++)
			{
				int x = t.peek().x;
				int y = t.poll().y;
				
				for(int j=0;j<4;j++)
				{
					int ax = x+xx[j];
					int ay = y+yy[j];
					
					if(ax >=0 && ax < n && ay >=0 && ay < m)
					{
						if(map[ax][ay] == 0 && visit[ax][ay] == 0)
						{
							map[ax][ay] = 1;
							t.offer(new TomatoLocation(ax, ay));
							visit[ax][ay] = 1;
						}
					}
				}
			}
			
			result_cnt++;
		}		
	}

}