[백준] 7578번: 토마토 (Java)

1. 문제설명

토마토는 격자 모양 상자의 칸에 하나씩 보관된다. 익은 토마토의 인접한(상하좌우) 곳에 있는 익지 않은 토마토들만 익은 토마토의 영향을 받아 익게 된다. 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구하는 문제이다.

만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력, 토마토가 모두 익지 못하는 상황이면 -1을 출력한다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

⇒ 모든 토마토가 익는 최소 시간을 구하는 문제 → BFS

• 토마토 정보를 담은 `int[][] box`를 사용한다.
• 상하좌우로 이동할 수 있는 배열(dx, dy)을 사용한다.
• 익은 토마토를 큐에 추가한다. (위치 정보)
• 큐가 빌 때까지
  • 큐에서 값을 꺼내, 이 위치의 상하좌우를 탐색한다. (`box[x][y]`)
  • 이동할 수 있는 위치이고, 익지 않은 토마토이면 (`box[nx][ny]`)
    • 날짜 계산을 위해 `box[nx][ny] = box[x][y] + 1`
    • 해당 토마토 위치를 큐에 추가한다.
• 안 익은 토마토가 있으면 -1을 출력
• `box`에서 max값을 구하고
  • 이 값이 1이면 처음부터 모든 토마토가 익어있는 상태로 0을 출력
  • 아니면 이 값에 -1한 값을 출력 (최종 날짜)

 

3. 다른 풀이

• 알고리즘 설계에 시간이 많이 걸려 다른 사람의 풀이를 참고했다.
  => https://stdio-han.tistory.com/91
• 토마토의 위치 정보와 날짜를 생성자를 통해 저장하고, 이것을 큐에 넣는 풀이도 있었다.
  => https://stdio-han.tistory.com/91

 

4. 최종 코드

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

public class Main {
    static int m, n; // 상자의 가로, 세로 칸의 수
    static int[][] box; // 상자
    static Queue<int[]> q = new ArrayDeque<>(); // 익은 토마토 저장할 큐

    static int[] dx = {-1, 1, 0, 0}; // 왼쪽, 오른쪽
    static int[] dy = {0, 0, -1, 1}; // 앞, 뒤

    static int bfs() {
        while(!q.isEmpty()) { // 큐가 빌 때까지
            int[] pos = q.poll(); // 큐에서 값 꺼냄
            int x = pos[0];
            int y = pos[1];
            for(int i=0; i<4; i++) { // 상하좌우 탐색
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<m) { // 이동 가능한 위치일 때
                    if(box[nx][ny] == 0) { //  다음 위치의 토마토가 익히지 않은 토마토일 때
                        box[nx][ny] = box[x][y] + 1; // 날짜 세기 위해 -> 현재 위치 값 + 1
                        q.add(new int[]{nx, ny}); // 큐에 다음 위치 추가
                    }
                }
            }
        }

        int day = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(box[i][j] == 0) { // 안 익은 토마토가 있는지 확인
                    return -1; // 결과값 1로 설정
                }
                day = Math.max(day, box[i][j]);
            }
        }

        if (day == 1) { // 처음부투 토마토가 모두 익어있으면
            return 0; // 결과값 0으로 설정
        } else { // 두 가지 조건에 모두 충족하지 않으면
            return day - 1; // 최종 날짜 설정
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        box = new int[n][m];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++) {
                box[i][j] = Integer.parseInt(st.nextToken());
                if(box[i][j] == 1) // 익은 토마토일 경우
                    q.add(new int[] {i, j}); // 해당 위치를 큐에 추가
            }
        }

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

 

5. 느낀점 or 기억할정보

확실히 골드 문제부터는 스스로 설계를 완벽하게 생각해내기가 어려웠다.

DFS로 푸는 방법이 익숙해져서 BFS로 풀이해야하는 문제가 있으면 더 어렵게 느껴지는 것 같다.

BFS로 푸는 연습이 더 필요한 것 같다.