[백준] 🥇 7576 토마토

📌 난이도

🥇 Gold 5

📌 문제

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

📌 풀이

와 지금까지의 BFS랑 결이 다른 문제였다.
확실히 난이도가 골드급 되는 문제를 푸니까, 지금까지의 BFS의 접근 방법과는 다르게 접근하는 문제가 나왔다.
지금까지는 단순히 start 지점에서 end 지점까지의 걸리는 시간같은 타입의 문제였는데, 이번에는 start가 여러개이고, end가 따로 없이 종료 시점을 정해줘야하는 문제였다.

그래서 처음 구현을 할때는 이전과 똑같이 구현을 했다가 오류가 생겼다.
바로 1이 여러개 있으면 동시에 퍼져나가야하는데, 앞의 주소값에 있는 1에서 다 퍼져나간후 뒤에를 검사하는 식으로 작동을 했다.
따라서 대체 어떻게 구현해야할까 고민을 하다가, 처음에는 이 BFS에 따로 curtime이라는 변수를 넣어주어서, box[i][j] == curtime일 때만 퍼져나가는 식으로 구현을 하였다.
하지만 그런식으로 하니까 시간복잡도가 o(n^3)이라는 말도 안되게 느린 알고리즘이 되어버렸다.

결국 고심한 끝에, 빈공간을 토마토가 걸리는 최대시간인 1000000 보다 많게 empty라는 상수를 만들어서 바꾸어주고, Math.min으로 빈공간과 채우는데 걸린시간을 비교해서 넣어주었다.
이런식으로하면 이미 값이 들어있어도 더 작은 시간이 들어가게 되므로, 코드가 결과적으로는 정상적으로 퍼진 것과 동일하게 된다.

이제 슬슬 상위 골드문제를 풀 시기가 온 것 같다. 😎

📌 Code

package BOJ.BFS;

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

public class N7576 {
    static int[][] box;
    static Queue<Integer[]> q;
    static int M;
    static int N;
    static int[] DR = new int[]{-1, 0, 1, 0};
    static int[] DC = new int[]{0, 1, 0, -1};
    static final int empty = 1000002;

    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];
        q = new LinkedList<>();

        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 Integer[]{i, j});
                } else if (box[i][j] == 0) {
                    box[i][j] = empty;
                }

            }
        }
        BFS();
        FindTomato();
    }

    static void FindTomato() {
        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                max = Math.max(max, box[i][j]);
            }
        }
        if (max == empty) {
            System.out.println(-1);
        } else {
            System.out.println(max - 1);
        }
    }

    static void BFS() {
        Integer[] cur;
        int nextRow;
        int nextCol;
        int curtime;
        while (!q.isEmpty()) {
            cur = q.poll();
            curtime = box[cur[0]][cur[1]] + 1;
            for (int i = 0; i < DC.length; i++) {
                nextRow = cur[0] + DR[i];
                nextCol = cur[1] + DC[i];
                if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M || box[nextRow][nextCol] != empty) {
                    continue;
                }
                q.add(new Integer[]{nextRow, nextCol});
                box[nextRow][nextCol] = Math.min(box[nextRow][nextCol], curtime);
            }
        }
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁