알고리즘 풀이 - 백준 7576(토마토, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

NxM 크기의 창고에 토마토를 보관 시, 익은 토마토의 인접 토마토는 1일 후 익을 때, 모든 토마토가 익는데 걸리는 일 수를 구하는 문제

 

 

2. 풀이

 

익은 토마토와 인접한 토마토가 익는 다는 것을 이용하여 인접한 정점을 탐색해나가는 그래프 탐색 문제이다.

이 문제는 익어 있는 상태의 토마토를 모두 미리 저장하고 주변의 토마토를 익혀가며 탐색을 수행해야 한다. 그러므로 인접한 것들을 탐색해가며 범위를 넓혀야 하므로 BFS 방식의 탐색을 수행해야 한다.

 

우선 미리 현재 익은 상태인 위치의 토마토를 Queue 자료구조에 저장한 뒤, 인접 정점들을 탐색하고 해당 인접 정점들을 다시 Queue에 넣는 방식으로 탐색을 수행한다.

 

그리고 각각의 토마토가 익은 날짜를 저장하는 배열을 따로 생성하고 그 값이 가장 큰 값을 출력하거나 익지 않는 토마토가 있으면 -1 출력하면 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    // 이동 가능 경우의 수(상하좌우)
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int m;
    static int n;
    static int[][] tomato;
    static int[][] day;
    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());
        tomato = new int[n][m]; // 토마토 정보 저장
        day = new int[n][m]; // 각 토마토가 익은 날짜 저장

        // 현재 익은 것을 Queue에 넣고 없는 토마토의 개수 별도 저장
        int ripe = 0;
        int noTomato = 0;
        Queue<int[]> q = new LinkedList<>();
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < m; j++){
                tomato[i][j] = Integer.parseInt(st.nextToken());
                if(tomato[i][j] == 1){
                    q.offer(new int[]{i, j});
                    ripe++;
                } else if(tomato[i][j] == -1){
                    noTomato++;
                }
            }
        }

        // 최대값을 구한다.
        int max = 0;
        while(!q.isEmpty()){
            int[] now = q.poll();
            int y = now[0];
            int x = now[1];

            for(int i=0; i < 4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];

                // 범위 안에 있고 아직 익지 않은 경우 탐색 수행
                if(0 <= ny && ny < n && 0 <= nx && nx < m && tomato[ny][nx] == 0){
                    tomato[ny][nx] = 1;
                    day[ny][nx] = day[y][x] + 1;
                    q.offer(new int[]{ny, nx});
                    ripe++;
                    
                    // max값 갱신
                    max = Math.max(max, day[ny][nx]);
                }
            }
        }

        // 전체 토마토 개수와 익은 개수가 같으면 max값을 쓰고 아니면 -1을 쓴다.
        System.out.println(ripe == n*m-noTomato ? max : -1);
        br.close();
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.