[골드5] 7576. 토마토 (Java)

https://www.acmicpc.net/problem/7576

7576번: 토마토

토마토는 20살 때 만 가넝,,

---

※  문제를 요약하면 아래와 같습니다.

▶ N x M 사이즈의 창고(배열)에 토마토의 상태가 -1 (없다), 0 (익지 않았다) 1(익었다) 로 표시

▶ 익은 토마토의 상,하,좌,우에 위치한 익지않은 토마토는 하루가 지나면 익은 상태로 변경  

▶  최초에 토마토의 상태가 주어졌을 때 창고 안에 모든 토마토가 익기 위해 걸리는 최소 며칠이 필요한지 출력 

▶  Input : 첫째 줄에 창고의 가로 길이 M, 세로 길이 N이 주어지고,  이후 N줄 만큼 각 줄의 토마토 상태 입력

▶  Output : 최소 날짜 출력, 모든 토마토가 익지 못하는 상황일 경우 -1 출력

---

◈ Input - 1

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

◈ Output - 1

8

◈ Input - 2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

◈ Output - 2

-1

◈ Input - 3

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

◈ Output - 3

6

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 익은 토마토 기준 상,하,좌,우의 토마토가 익는다 == 노드에서 다음레벨들의 상태를 탐색하여 0일 경우 1로바꾼다.

▶ 다음 레벨들의 상태 탐색 == BFS

▶ 익은 토마토가 여러 개일 경우 == BFS의 시작 점이 여러 곳

▶ 최초에 익은 토마토의 갯수 만큼 큐의 배열을 만들어 동일한 타이밍에 한레벨씩 탐색

▶ 방문하지 못한 곳이 있다 == 안익은 토마토가 있다 == -1 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
	int nRow;
	int nCol;

	public Point(int nRow, int nCol) {
		this.nRow = nRow;
		this.nCol = nCol;
	}
}

public class Main {
	static BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
	static boolean[][] barrVisited;
	static int[][] narrTomatos;
	static int nDay = 0;
	static int N, M;

	public static void main(String[] args) throws IOException {

		// 대박 대박 대박
		System.setIn(new FileInputStream(Main.class.getResource("input.txt").getPath()));

		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		M = Integer.parseInt(st.nextToken()); // cols
		N = Integer.parseInt(st.nextToken()); // rows

		barrVisited = new boolean[N][M];
		narrTomatos = new int[N][M];
		
		ArrayList<Point> listPoint = new ArrayList<>();
		// 토마토 상태 입력받구
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bReader.readLine());
			for (int j = 0; j < M; j++) {
				narrTomatos[i][j] = Integer.parseInt(st.nextToken());

				// 토마토가 자라나는 시작점 추가
				if (narrTomatos[i][j] == 1)
					listPoint.add(new Point(i, j));
				else if (narrTomatos[i][j] == -1)
					barrVisited[i][j] = true; // 방문할 필요가 없다아
			}
		}

		// 탐색합시당
		BFS(listPoint);

		// 어딘가 탐색 안된 곳이 있다 ? == 토마토가 안익은데가 있다
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!barrVisited[i][j]) {
					nDay = -1;
					break;
				}
			}
			if(nDay==-1)
				break;
		}
		
		bWriter.write(String.valueOf(nDay));

		bWriter.flush();
		bWriter.close();
	}

	public static void BFS(ArrayList<Point> listPoint) throws IOException {

		Queue<Point>[] queueBfs = new LinkedList[listPoint.size()];
		// 시작 점이 여러 개일 수도 있으니,
		// 큐 배열로 선언해놓자.
		for (int i = 0; i < listPoint.size(); i++) {
			queueBfs[i] = new LinkedList<>();
			queueBfs[i].add(listPoint.get(i));
		}

		// 동 서 남 북 델타 돌리자
		int dr[] = { 0, 0, 1, -1 };
		int dc[] = { 1, -1, 0, 0 };

		// 하루에 하나씩이니까 탐색 후 다음 노드 대체 저장소를 하나 만들어주자
		Queue<Point> qNextNodes = new LinkedList<>();
		
		boolean bAllEmpty = false;
		// BFS 돌려볼까유~
		while (!bAllEmpty) {
			boolean bIsEmpty = true;
			for (int i = 0; i < listPoint.size(); i++) {
				// 토마토가 자라난다..
				
				while (!queueBfs[i].isEmpty()) {
					Point p = queueBfs[i].poll();
					// 상하좌우 탐색 후 0이면 1로 바꿔주고
					// queue탐색 고고합시다
					if (!barrVisited[p.nRow][p.nCol]) {

						barrVisited[p.nRow][p.nCol] = true;
						for (int k = 0; k < dr.length; k++) {
							int nSearchRow = p.nRow + dr[k];
							int nSearchCol = p.nCol + dc[k];
							
							// 토마토 익는다.
							if (nSearchRow >= 0 && nSearchCol >= 0 && nSearchRow < N && nSearchCol < M
									&& narrTomatos[nSearchRow][nSearchCol] == 0 && !barrVisited[nSearchRow][nSearchCol]) {
								qNextNodes.add(new Point(nSearchRow, nSearchCol));
								narrTomatos[nSearchRow][nSearchCol] = 1;
							}
						}
					}
				}

				// 탐색 끝났다아
				if(bIsEmpty && !qNextNodes.isEmpty())
					bIsEmpty = false;
				
				while (!qNextNodes.isEmpty()) {
					queueBfs[i].add(qNextNodes.poll());
				}
				
			}
			bAllEmpty = bIsEmpty;
			//System.out.println(Arrays.deepToString(barrVisited));
			// 다 탐색했다
			if(bAllEmpty)
				break;
			
			// 하루가 지났따
			nDay++;
		}

	}
}

Good Luck! (피드백 감사합니다!)