백준(Backjoon) 7576, 토마토

문제풀이

위 문제를 해결하기 위해서는 그래프 알고리즘은 BFS 그래프 탐색 알고리즘을 활용합니다. 

 

수행과정

1. 토마토 상자안에 존재하는 익은 토마토(1)의 좌표를 큐에 삽입한다.
2. 큐의 사이즈가 0이 될때까지 BFS 탐색을 수행한다.
3. 큐에서 꺼낸 익은 토마토(1)의 인접 위치(상하좌우)를 검사하고 토마토 상자 범위안에 있고 익지 않은 토마토(0)인지를 검사한다.
4. 만약 올바른 인접한 익지 않은 토마토(0)라면 익은 토마토(1)의 익지 않은 토마토(0)의 좌표의 값은 인접탐색 기준 토마토 좌표에 해당하는 값 + 1이 된다.
5. 익지 않은 토마토(0)의 좌표값을 큐에 다시 삽입한다.
6. 2~5의 과정을 반복 수행한다.

예시

예제 입력3을 기준으로 수행한다.

 

주의점

1. BFS 탐색을 종료했음에도 불구하고 토마토 상자 안에 익지 않은 토마토(0)가 존재하는 경우 -1을 반환한다.
2. 토마토 상자안이 이미 익은 토마토(1)로만 존재하는 경우 0을 반환한다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
	
	// 상하좌우
	private static int[] dr = {-1,1,0,0};
	private static int[] dc = {0,0,-1,1};
	private static int[][] map;
	private static int m, n;
	
	static class Tomato{
		int y, x;

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

		@Override
		public String toString() {
			return "Tomato [y=" + y + ", x=" + x + "]";
		}		
	}
	
	public static boolean check_adjust(Tomato t)
	{
		int x = t.x;
		int y = t.y;
		
		// 범위를 벗어나지 않고 인접 토마토의 상태가 0인 경우 
		if(!(x<0 || x>m-1 || y>n-1 || y<0) && map[y][x]==0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	
	public static void bfs(Queue<Tomato> queue)
	{
		while(!queue.isEmpty())
		{
			Tomato t = queue.poll();
			
			for(int i=0;i<4;i++)
			{
				int ny = t.y + dr[i];
				int nx = t.x + dc[i];
				Tomato adj_tomato = new Tomato(ny, nx);
				
				if(check_adjust(adj_tomato))
				{
					map[ny][nx] = map[t.y][t.x] + 1;
					queue.add(adj_tomato);
				}
			}
		}
	}

	public static int solution()
	{
		Queue<Tomato> queue = new LinkedList<Tomato>();
		int answer = 0;
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<m; j++)
			{
				if(map[i][j]==1)
				{
					queue.add(new Tomato(i, j));
				}
			}
		}
		
		bfs(queue);
		
		
		for(int i=0;i<n; i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map[i][j]==0)	// 익지 않은 토마토가 존재하는 경우
				{
					return -1;
				}
				if(answer < map[i][j])	// map에서 가장 큰 일수를 구한다.
				{
					answer = map[i][j];
				}
			}
		}
		// 최종일수에서 하루를 뺀다. 기본값이 1부터 시작하기 때문이다.
		return answer-1;
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str[] = br.readLine().split(" ");
		m = Integer.parseInt(str[0]);
		n = Integer.parseInt(str[1]);
		
		map = new int[n][m];
		
		for(int i=0;i<n;i++)
		{
			map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		}
		
		System.out.println(solution());
		
	}
}

References

[백준 7576, c++] 토마토(bfs), https://jdselectron.tistory.com/55