[BOJ] 7576. 토마토
16 Apr 2026
Reading time ~4 minutes
풀이
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N,M;
static int[][] map;
static boolean[][] check;
static int[][] dist;
static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
map = new int [N][M];
check = new boolean [N][M];
dist = new int [N][M];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
}
}
Queue<Point> q = new LinkedList<>();
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 1) {
q.add(new Point(i,j));
check[i][j] = true;
}
}
}
while(!q.isEmpty()) {
Point p = q.poll();
for(int i = 0; i < dy.length; i++) {
int ny = p.y + dy[i];
int nx = p.x + dx[i];
if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if(!check[ny][nx] && map[ny][nx] == 0) {
q.add(new Point(ny,nx));
check[ny][nx] = true;
dist[ny][nx] = dist[p.y][p.x]+1;
}
}
}
int ans = Integer.MIN_VALUE;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
ans = Math.max(ans,dist[i][j]);
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0 && dist[i][j]==0) ans = -1;
}
}
System.out.println(ans);
}
static class Point {
int y,x;
Point(int y, int x){
this.y = y;
this.x = x;
}
}
}
2중 for문을 이용하여 익은 토마토중에 가장 오랜 시간이 걸린 토마토의 값을 정답 ans에 저장한다. 끝까지 익지 않은 토마토가 있다면 정답 ans에 -1을 저장한다.
이때 정답 ans를 구하는 로직에서 if문 안에 있는 내용은 각각 다음을 뜻한다. map[i][j] == 0은 원래 익지 않았다. dist[i][j] == 0은 영향을 받지 않았다. 따라서 원래 익지 않은 토마토가 영향을 받지 않았다면 끝까지 익지 않았으므로 -1을 출력한다.
잘못된 풀이
몇일 뒤에 다시 풀어보았더니 아래와 같은 실수가 나왔다. 무엇이 문제인지 알아봤더니 다음과 같았다. DFS와 BFS 문제의 풀이 소스에 있는 대로 BFS의 기본 함수를 외워서 적용하려 했던 게 문제였다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int M,N;
static int[][] map;
static boolean[][] check;
static int[][] dist;
static int[] dy = {1, 0, -1, 0};
static int[] dx = {0, 1, 0, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
map = new int[N][M];
check = new boolean[N][M];
dist = new int[N][M];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
map[i][j] = sc.nextInt();
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 1 && !check[i][j]) {
check[i][j] = true;
bfs(new Point(i,j));
}
}
}
int ans = Integer.MIN_VALUE;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
ans = Math.max(ans,dist[i][j]);
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(map[i][j] == 0 && dist[i][j] == 0) ans = -1;
}
}
System.out.println(ans);
}
static void bfs(Point p) {
Queue<Point> q = new LinkedList<>();
q.add(p);
check[p.y][p.x] = true;
while(!q.isEmpty()) {
p = q.poll();
for(int i = 0; i < dy.length; i++) {
int ny = p.y + dy[i];
int nx = p.x + dx[i];
if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if(!check[ny][nx] && map[ny][nx] == 0) {
q.add(new Point(ny,nx));
check[ny][nx] = true;
dist[ny][nx] = dist[p.y][p.x]+ 1;
}
}
}
}
static class Point {
int y,x;
Point(int y, int x) {
this.y = y;
this.x = x;
}
}
}
예를 들어 아래 테스트 케이스에서 정답이 9로 나온다. 원래는 정답이 6이 나와야 한다. 습관처럼 첫 번째 지점(0,0)을 큐에 넣는 부분까지 bfs 함수에 넣게 되었다. 그리 하였더니 그 다음으로 바로 큐에 들어갔어야 할 두 번째 지점(5,3)이 나중에 들어가게 되었다. (0,0) 한 개 지점을 큐에 넣자마자 bfs를 바로 수행하기 때문에 (5,2) 지점의 dist값이 9로 셋팅 된다. 그 후 (5,3) 지점을 큐에 넣는다. 그리하여 정답이 9로 잘못 출력되었다.
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
이 문제는 DFS로는 풀 수 없는 데 그 이유를 간접적으로 나마 느끼게 되었다.