[백준 7576] 토마토

문제 출처

사용 언어:Java

1. 구상

• 익은 토마토의 상하좌우에 있는 안 익은 토마토들은 영향을 받아 익음
  
  → 익은 토마토의 상하좌우를 확인하여 안 익은 토마토가 있다면 익은 토마토로 표시
  
  → 따로 방문 표시를 하지 않고 밭에 걸린 날짜값 기록
  
  → 밭을 탐색하면서 날짜값의 최대로 갱신하고, 다 익지 않았거나 이미 익었다면 각각 -1, 0 반환
  
  일부 알고리즘 및 코드 참고

2. 구현

import java.util.*;
import java.lang.*;
import java.io.*;


//토마토 위치를 기록하는 tomato 클래스 생성
class tomato {
	int x;
	int y;
	
	public tomato (int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class sol_7576 {
    //토마토 밭
	static int[][] map;
	//M = 가로, N = 세로
	static int M, N;
	//bfs를 이용하기 위한 큐
	static Queue<tomato> queue;
	//상하좌우로 이동하기 위한 x좌표, y좌표 이동수
	static int[] nextX = {-1, 1, 0, 0};
	static int[] nextY = {0, 0, -1, 1};
	
	public static void main(String[] args) throws NoSuchElementException, IOException {
		Scanner s = new Scanner(System.in);		
		
		M = s.nextInt();
		N = s.nextInt();
		
		map = new int[N][M];
		queue = new LinkedList<tomato>();
		
		//토마토 밭 입력 받기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = s.nextInt();
				
				//만약 익은 토마토라면 큐에 넣기
				if (map[i][j] == 1)
					queue.add(new tomato(i, j));
			}
				
		}
			
		
		System.out.println(bfs());
		
	}
	
	//bfs를 이용하여 최소로 걸리는 익은 날짜 구하기
	static int bfs () {
		//큐가 빌 때까지 실행
		while (!queue.isEmpty()) {
			//큐의 앞 부분 원소 가져오기
			tomato t = queue.remove();

			int nowX = t.x;
			int nowY = t.y;

			//현재 위치에서 상하좌우 탐색
			for (int i = 0; i < 4; i++) {
				int x = nowX + nextX[i];
				int y = nowY + nextY[i];

				//밭 범위에 있고 안 익은 토마토라면 익히고 큐에 넣기
				if (x >= 0 && y >= 0 && x < N && y < M ) {
					if (map[x][y] == 0) {						
						queue.add(new tomato(x, y));	
						map[x][y] = map[nowX][nowY] + 1;				
					}
				}
				
			}
		}
		
		int result = Integer.MIN_VALUE;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				//안익은 토마토가 있다면 -1 반환
				if (map[i][j] == 0) {
					return -1;
				}
				
				//탐색하면서 날짜값 갱신하기
				result = Math.max(result, map[i][j]);				

			}
		}

		//토마토 밭의 토마토가 다 익어있었다면 0 반환
		if (result == 1) {
			return 0;
		}
		
		else {
			return result - 1;
		}
	}
}