[백준 BOJ/Gold V] 7576번 : 토마토

 

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

7576번: 토마토

 

재밌는(?) 문제였다

문제와 예제 입/출력을 보면서 생각했던것들을 정리해보자면

 

 

문제

- 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 
- 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라.
- 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

입력

- 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다.
- 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

출력

- 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.
- 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

 

 

1. 인접한 상,하, 좌, 우를 확인하며 모두 익을 떄까지의 최소 날짜를 출력 → BFS를 이용해야한다!

 

2. 토마토가 모두 익지 못하는 상황이면 -1을 출력해야하는데 

바로 이런 상황일때다

0 상하좌우 모두에 -1만 있다면 끝까지 바뀌지 않는 0이 남게 되고 최종 답은 -1이 된다

(어느 한 방향도 열려있지 않다면!)

 

3. 아예 계산을 안해줘도 되는 경우도 있다

박스에 0이 아예 존재하지 않는다면 익는걸 기다릴 필요가 없기 때문에 최종 답은 0이 된다

 

4. 이 문제는 처음에 어떤 고정된 한 칸에서 BFS를 시작하는게 아니라 1이 있는 모든 칸에서 동시에 진행이 되어야한다

이렇게 1이 (0, 0) (3,5) 두 칸에 있다면 하루 지난 후 동시에 주변이 익기 때문에 큐에 두 칸을 모두 넣고 시작해야한다

 

 

---

 

- 다 입력받은 후 박스에 0이 있는지없는지 확인하면 한번 더 이중for문을 돌아야하고, 마찬가지로 1이 있는 자리도 입력받은 후에 다시 이중for문을 돌면서 알아내려고 하면 한번 더 돌아야하기 떄문에

3,4번 확인은 처음에 입력받을때 하는게 좋을거라고 생각했다

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});
                else if (box[i][j] == 0) count++;
            }
        }

 

그래서 이렇게 입력받으면서 1이면 큐에 추가해주고 0이면 count++ 해주었다

다 입력받은 후에 count 값이 0 이라면 0이 없는거기 때문에 다른 계산을 해주지 않아도 되고 result = 0 이 된다!

 

 

- count !=0 인 경우 BFS를 이용하여 확인해주는데 상하좌우를 보면서 0이라면 값을 +1씩 해주고 큐에 추가해준다

마지막으로 늘려준 값(=최소 날짜)을 가지고 돌아가야하기때문에 max값을 계속 갱신해주었다

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}); // 큐에 넣어주기

                        max = Math.max(max, box[nx][ny]);
                    }
                }

 

 

- BFS를 돌고 온 후 한번 더 확인하는 절차를 가져야한다

전체를 다시 확인하다가  0이 발견되면 모두 익지 못하는 상황이기 때문에 result = -1 로 하고 for문을 빠져나간다

- 0이 발견되지 않는다면 최종 답은 max - 1 이 된다 BFS를 돌때 0이 발견되면 현재 값에 +1 해준걸 넣었는데 1일차에 2부터 들어갔기 때문에 하루씩 더 늘어나있는 상황이기 때문이다

	loop:
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {

                    if(box[i][j] == 0) { // bfs 돌고왔는데 0 남아있으면 안 익은게 남아있다면
                        result = -1;
                        break loop; // 결과를 -1로 만들고 종료

                    } else {
                        result = max - 1; // 처음에 2부터 넣었기 때문에 최종답은 max-1 해야됨
                    }
                }
            }

 

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int M; // 상자 가로 칸, y
    static int N; // 상자 세로 칸, i
    static int[][] box;
    static int count = 0; // 입력할때 0이 있는지 없는지 확인하는 용도
    static Queue<int[]> q = new LinkedList<>();
    static int max = 0;
    static int result = 0;

    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});
                else if (box[i][j] == 0) count++;
            }
        }

//        System.out.println(Arrays.deepToString(box));
//        System.out.println(count);
//        while(!q.isEmpty()) {
//            int[] qq = q.poll();
//            System.out.println(Arrays.toString(qq));
//        }

        if(count != 0) { // count = 0 이면 전체가 익어있는 상태라서 확인할 필요가 없음 -> result = 0
            bfs();

            loop:
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {

                    if(box[i][j] == 0) { // bfs 돌고왔는데 0 남아있으면 안 익은게 남아있다면
                        result = -1;
                        break loop; // 결과를 -1로 만들고 종료

                    } else {
                        result = max - 1; // 처음에 2부터 넣었기 때문에 최종답은 max-1 해야됨
                    }
                }
            }
        }

        System.out.println(result);
    }

    static void bfs() {

        while (!q.isEmpty()) {
            int[] xy = q.poll();
            int x = xy[0];
            int y = xy[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}); // 큐에 넣어주기

                        max = Math.max(max, box[nx][ny]);
                    }
                }
            }
        }
    }
}

 

한번에 이중for문 빠져나가는 방법은 몰랐는데 이번에 알게되어서 좋다!! 원래는 break 하고 또 break 하고 이랬는데 한번에 빠져나갈 수는 없을까 하고 찾아보니 있었다 역시👍👍

그리고 BFS에 대한 두려움을 이제 극복한거같다 더 많이 풀어봐야겠다😎😎