[백준] no7576: 토마토

문제

가로 M, 세로 N 크기의 박스에 각 칸마다 토마토가 주어진다.

0 : 안익은 토마토

1 : 익은 토마토

-1 : 빈칸

하루에 한번씩 익은 토마토(1) 상하좌우에 있는 안익은 토마토(0)가 익는다. (즉, 1 상하좌우에 있는 0이 1이 된다)

총 몇일 뒤에 안익은 토마토가 전부 익는지 구해라

단, 모든 안익은 토마토가 다 익을 수 없는 환경이면 -1을 출력(0의 상하좌우가 -1인 경우)

문제 링크 : https://www.acmicpc.net/problem/7576

---

원리

BFS

---

풀이방법

1. 토마토 객체 클래스 : 좌표값과 함께 몇일날 익었는지 표시할 day를 추가

2. 이중배열로 box를 만들어 맨 처음 입력받은 토마토 세팅

3. Deque를 이용한 대기열을 만들고, 처음 입력된 익은 토마토(1)들을 전부 넣음

   이 때, 안익은 토마토도 총 몇개인지 count파악해줌. (만약 0의 개수 = N*M이면 바로 0 출력)

4. 상하좌우를 탐색할 것이니 총 4번씩 반복할 것이며, 이를 위해 좌표를 상하좌우 움직임을 만들어줄 static배열 만들어줌

   가로방향 {+1 , -1 , 0 , 0} | 세로방향 {0, 0, +1, -1} 이면, i는 곧 두 배열의 인덱스이므로

   1번째 반복 때 x+1 = 우

   2번째 반복 때 x-1 = 좌

   3번째 반복 때 y+1 = 하

   4번째 반복 때 y-1 = 상

5. 만약 해당 위치가 0이면 1로 바꿔주고, 몇일째에 바뀌었는지 저장해서 대기열에 넣어줌

    동시에 익으면 안익었던 토마토 개수에서 1씩 빼줌

6. 반복마다 해당 토마토가 몇일날 익은 앤지 day를 업데이트 해줌

7. 대기열의 모든 토마토 처리 후, 안익은 토마토가 남았으면 -1출력

8. 다 처리하고 0이 없으면 day 출력

---

나의 코드

1. 브루트 포스(?) [ 실패 ]

: Box 1회 순회 당 1인 겨웅 상하좌우를 탐색해서 0이면 1로 바꿔주고 현위치를 2로 바꿔줌

  (한 번에 여러번 바뀌는 경우를 방지하기 위함)

: 1회 반복임을 count 해주고 난 후, 다음 반복을 위해 2를 1로 다시 바꿔줌

  (다음 순회시 다시 count해줄 수 있도록 해주기 위함)

 

2. BFS

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    /**
     * 1. 처음 입력때 0의 개수 파악
     * 2. 만약 0이 없으면  바로 0을 출력(처음부터 모두 익은상태)
     * 3. 반복을 하면서 1이 있는 위치의 상하좌우에 0이 있으면 1로 바꾸고 바뀌는 개수만큼 count, 1회 반복당 count+1, 바꾼 개수만큼 0의 개수에서 빼줌
     * 4. 만약 1로 바뀌는 개수가 0인데, 0의 개수가 0보다 크면 더이상 못바꾸는 경우이므로 -1 출력
     */

    static int M;
    static int N;
    static int zero;
    static int[][] box;
    static int[] horizontal = {1, -1, 0, 0};
    static int[] vertical = {0, 0, 1, -1};

    public static class Tomato {
        private int x;
        private int y;
        private int day;
        public Tomato(int x, int y, int day) {
            this.x = x;
            this.y = y;
            this.day = day;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        box = new int[M][N];

        for(int i=0; i<M ; i++) {
            StringTokenizer line = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++) {
                int tomato = Integer.parseInt(line.nextToken());
                box[i][j] = tomato;
                if(tomato==0) zero++;
            }
        }
        if(zero==0) System.out.println(0);
        else System.out.println(BFS());
    }

    private static int BFS() {
        Deque<Tomato> dq = new ArrayDeque<>(); // 검수할 토마토 위치를 담는 대기열
        int day = 0;  // 최종 반환 값

        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(box[i][j]==1) dq.add(new Tomato(i,j, 0));
            }
        }

        /**
         * BFS 반복 시작
         */
        while(!dq.isEmpty()) {
            Tomato now = dq.poll();
            day= now.day; // 매 4방향 반복마다 +1의 데이가 Tomato 객체 안에 쌓임

            for(int i=0 ; i<4 ; i++) {
                int nowX = now.x + horizontal[i]; // 천잰데??
                int nowY = now.y + vertical[i];  // 0~3반복하는동안 각각 X축 Y축으로 +1과 -1로 상하좌우 도는 방법

                if(0<=nowX && nowX<M && 0<=nowY && nowY<N) {  // box 범위 내일 때
                    if(box[nowX][nowY]==0) {
                        box[nowX][nowY] = 1;
                        dq.add(new Tomato(nowX, nowY, day+1));
                        zero--;
                    }
                }
            }
        }

        // 만약 box에 0이 남아있는 경우
        if(zero!=0) day= -1;

        return day;
    }
}

 

---

레퍼런스 코드

참고 링크 : https://bcp0109.tistory.com/9