[BOJ_7576] 토마토

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

7576번: 토마토

🏗️ 설계

현재 익은 토마토들을 Queue에 넣고 근처 Queue들의 값을 들어있는 Queue의 값에 1씩 더해주며 최종적으로 나오는 가장 큰 값 - 1을 함으로써 다 익을 때까지 걸리는 시간을 구하고자 하였습니다.

📋 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int rowLen, colLen;
	static int[][] board;

	static class Pair {
		int first;
		int second;

		public Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}

	public static boolean check(int row, int col) {
		return row >= 0 && row < rowLen && col >= 0 && col < colLen;
	}

	public static int bfs() {
		int max = 1;

		Queue<Pair> q = new ArrayDeque<>();

		int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

		for (int i = 0; i < rowLen; i++) {
			for (int j = 0; j < colLen; j++) {
				if (board[i][j] == 1)
					q.add(new Pair(i, j));
			}
		}

		while (!q.isEmpty()) {
			Pair tmp = q.poll();

			for (int i = 0; i < 4; i++) {
				int nextRow = tmp.first + dir[i][0];
				int nextCol = tmp.second + dir[i][1];

				if (check(nextRow, nextCol) && board[nextRow][nextCol] == 0) {
					q.add(new Pair(nextRow, nextCol));
					board[nextRow][nextCol] = board[tmp.first][tmp.second] + 1;

					if (board[nextRow][nextCol] > max)
						max = board[nextRow][nextCol];
				}
			}
		}

		for (int i = 0; i < rowLen; i++) {
			for (int j = 0; j < colLen; j++) {
				if (board[i][j] == 0)
					return -1;
			}
		}
		return max - 1;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		colLen = Integer.parseInt(st.nextToken());
		rowLen = Integer.parseInt(st.nextToken());

		board = new int[rowLen][colLen];

		for (int i = 0; i < rowLen; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < colLen; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		System.out.println(bfs());
	}

}

⏰ 사용한 메모리 / 시간

• Memory : 103432KB
• Time : 644ms