[Java] 백준(골드-5) 7576번 - 토마토

문제 풀이

---

이 문제는 일반적인 BFS의 솔루션을 조금 응용하면 된다.

아이디어 도출

BFS 솔루션을 어떻게 응용할 수 있을까?

일반적인 BFS 풀이 경험을 빗대어보면, 주어지는 입력 2차원 배열의 (0,0) 위치에서 순차적으로 BFS를 호출해간다. 그런데 이번 문제는 (0,0) 위치에서부터 순서대로 BFS를 호출하면 안된다. 왜냐하면 익은 토마토가 1개 이상 주어지고, 익은 토마토의 위치인 (nx, ny)마다 BFS를 통해 상하좌우로 탐색하여 탐색한 노드마다 깊이를 저장해야 하기 때문이다.

이를 통해 생각해낸 아이디어는 다음과 같다.

• BFS 함수 내에서 Queue를 초기화하고 쌓고 제거하는 것이 아니라, 전역에서 Queue를 선언하고 익은 토마토 위치를 사전에 담아둔 후 BFS 탐색을 실행한다.
• 위 솔루션대로 BFS 작업을 마친 후, 토마토 창고인 2차원 배열에 익지 않은 토마토가 1개 이상 있다면 -1을 출력한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {
    // BFS에서 x, y좌표마다 상하좌우로 이동할 배열 선언
    static int[] dx = new int[]{0, 1, 0, -1};
    static int[] dy = new int[]{1, 0, -1, 0};

    // BFS 함수 내에서 초기화하지 않고 전역으로 선언
    static Queue<int[]> q = new LinkedList<>();

    // 방문 배열로 사용할 2차원 배열 선언
    static boolean[][] visited;
    
    // 배추의 위치를 저장할 2차원 배열 선언
    static int[][] arr;

    // 토마토 창고 크기를 저장할 N, M 선언
    static int N;
    static int M;

    // BFS가 호출되면서 토마토 창고 위치에 저장할 깊이 변수 선언
    static int depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        // 방문 배열과 토마토 창고 배열 초기화
        visited = new boolean[N][M];
        arr = new int[N][M];

        // 입력 값에서 공백값을 제외하고 arr에 저장
        for(int i=0; i<N; i++) {
            String[] str = br.readLine().split(" ");
            for(int j=0; j<str.length; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        
        // 토마토 창고 배열을 탐색하며 노드별 깊이를 저장할 depth 초기화
        depth = 0;

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                // 방문하지 않았고 토마토의 위치라면
                // ** 방문 여부를 체크하고 큐에 토마토 위치를 담는다.
                // 0,0 위치부터 순차적으로 BFS 함수를 호출하지 않고 큐에 담아두는 이유는
                // 먼저 큐에 토마토 위치를 담아두고 BFS 함수를 호출해야만 
                // 익은 토마토 위치에서부터 BFS를 통해 탐색하며 최소 일수를 구할 수 있기 때문이다.
                if(!visited[i][j] && arr[i][j] == 1) {
                    visited[i][j] = true;
                    q.offer(new int[]{i, j});
                }
            }
        }
        
        // 큐에 익은 토마토 위치를 모두 담은 후 BFS 호출
        BFS();

        // 만약 토마토 창고에 익지 않은 토마토가 1개 이상 있다면 -1을 출력 
        for(int[] a : arr) {
            for(int num : a) {
                if(num == 0) {
                    depth = -1;
                }
            }
        }

        bw.write(depth+"\n");
        
        bw.close();
        br.close();
    }

    static void BFS() {
        // BFS 함수 내에서 큐를 초기화하여 노드 탐색하지 않고
        // 모든 토마토 위치에서 BFS를 호출해야 한다.
        while(!q.isEmpty()) {
            int[] now = q.poll();
            for(int dir=0; dir<4; dir++) {
                int i = now[0] + dx[dir];
                int j = now[1] + dy[dir];
                if(0<=i && 0<=j && i<N && j<M) {
                    if(!visited[i][j] && arr[i][j] == 0) {
                        visited[i][j] = true;
                        arr[i][j] = arr[now[0]][now[1]]+1;
                        // BFS로 탐색하면서 깊이를 카운트하여 depth에 저장
                        depth = arr[now[0]][now[1]];
                        q.add(new int[]{i, j});
                    }
                }
            }
        }
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.