[ 백준 7576 ] 토마토

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

7576번: 토마토

2. 문제

3. 문제 요약

 2차원 배열 Box에 담겨있는 토마토가 모두 익게되는 일수를 출력한다.

 

4. 문제 풀이

(1)  BFS

  익어있는 토마토 '1'에 인접해있는 익지 않은 토마토 '0'들을 모두 익게하는 문제이다.

  날짜를 depth로 두고 푼다면, 각 depth마다, 현재의 토마토의 인접 영역들을 모두 '1'로 바꿔주면 된다.

  따라서, 상하좌우를 인접노드로 삼는 그래프를 만드는 방식으로 접근했다.

 

(2) Queue 

   불필요한 중복 연산을 없애기 위해서, Queue를 이용했다.

   Queue에 담기는 데이터는 위치(row, col)와 일수(d), 총 3가지의 정보를 저장하도록 했다.

   이를 통해, 다음에 탐색할 데이터들을 queue에 저장하고, 꺼내오는 과정을 통해서

   접근 가능한 모든 익지않은 토마토'0'을 '1'로 바꾸어 나간다.

  

(3) 카운터

  데이터를 입력받는 과정에서 익지않은 토마토'0'의 갯수(cnt)를 저장하고,  

  Queue를 이용해서 '0'을 '1'로 바꿀때마다, 익지 않은 토마토의 수를 줄여나갔다.(cnt--)

  더 이상 Queue에 담긴 데이터가 없음에도 cnt가 0이 아니라면,

  접근 불가능한 토마토가 있으므로 '-1'을 출력하고, 그것이 아니라면 해당 뎁스'd'를 출력하도록 했다.

 

 

 

5. 풀이 코드

public static void main(String[] args) throws Exception {
    StringTokenizer stk = new StringTokenizer(br.readLine());
    int M = Integer.parseInt(stk.nextToken());
    int N = Integer.parseInt(stk.nextToken());
    box = new int[N + 2][M + 2];
    Queue q = new Queue(N * M);
    for (int r = 1; r <= N; r++) {
        stk = new StringTokenizer(br.readLine());
        for (int c = 1; c <= M; c++) {
            box[r][c] = Integer.parseInt(stk.nextToken()) + 1;
            if (box[r][c] > 1) {
                q.enque(r, c, 0);
            } else {
                cnt += box[r][c];
            }
        }
    }
    int ans = bfs(q);
    bw.write((cnt == 0 ? ans : -1) + "");
    bw.flush();
}Colored by Color Scripter

static int bfs(Queue q) {
    int R, C, D = 0;
    while (!q.isEmpty()) {
        int[] pos = q.deque();
        R = pos[0];
        C = pos[1];
        D = pos[2];
        for (int d = 0; d < 4; d++) {
            int nR = R + dR[d];
            int nC = C + dC[d];
            if (box[nR][nC] != 1)
                continue;
            cnt--;
            box[nR][nC] = 2;
            q.enque(nR, nC, D + 1);
        }
    }
    return D;
}
 

class Queue {
    int front;
    int last;
    int[][] queue;
 
    public Queue(int size) {
        this.front = -1;
        this.last = -1;
        this.queue = new int[size][3];
    }
 
    public void enque(int r, int c, int d) {
        ++last;
        queue[last][0] = r;
        queue[last][1] = c;
        queue[last][2] = d;
    }
 
    public int[] deque() {
        return queue[++front];
    }
 
    public boolean isEmpty() {
        return front == last;
    }
}Colored by Color Scripter