문제출저 : www.acmicpc.net/problem/7576
7576번: 토마토
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토�
www.acmicpc.net
풀이 과정
- pair객체는 필드를 3개 가진다. 좌표(row, col)와 date. 여기서 date는 bfs를 하면서 +1씩되는 날짜를 의미
- 익은 토마토를 미리 찾아놓고 Queue에 저장.
- 저장한 토마토를 하나씩 꺼내면서 BFS시작.
- BFS과정을 거치면 날짜가 1씩 커지면서 모든 토마토를 익게하고, 다익었다는 가정하에 가장 큰 maxDate가 정답.
소스코드
package 백준;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Ex_7576 {
// 실버1 토마토 bfs 문제 https://www.acmicpc.net/problem/7576
private static class Pair {
int row;
int col;
int date;
public Pair(int row, int col, int date) {
this.row = row;
this.col = col;
this.date = date;
}
}
private static int N;
private static int M;
private static int[][] map;
private static int maxDate = 0;
private static Queue<Pair> q = new LinkedList<Pair>();
private static int[] dr = { -1, 1, 0, 0 };
private static int[] dc = { 0, 0, -1, 1 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[N][M]; // 인덱스에 맞추기위해서
for (int row = 0; row < N; row++) {
st = new StringTokenizer(br.readLine(), " ");
for (int col = 0; col < M; col++) {
map[row][col] = Integer.parseInt(st.nextToken());
if (map[row][col] == 1) { // 1을 미리 찾아 놓는다.
q.offer(new Pair(row, col, 0));
}
}
}
bfs(); // 이 메소드를 거치면 maxDate에 토마토를 다 익히는데 며칠이 걸리는지가 저장됨
// 답 체크
boolean check = true;
outerloop: for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
if (map[row][col] == 0) {
check = false;
break outerloop;
}
}
}
int answer = check ? maxDate : -1;
bw.write(answer + "");
bw.close();
br.close();
}
private static void bfs() {
while (!q.isEmpty()) {
Pair temp = q.poll();
maxDate = Math.max(maxDate, temp.date);
for (int i = 0; i < 4; i++) {
int tr = temp.row + dr[i];
int tc = temp.col + dc[i];
if (tr >= 0 && tc >= 0 && tr < N && tc < M && map[tr][tc] == 0) {
map[tr][tc] = 1;
q.offer(new Pair(tr, tc, temp.date + 1));
}
}
}
}
}