[백준] 7576: 토마토 - Java (그래프)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

  접근 방식

 

비교적 친근한 BFS를 통해 접근하려고 한다. 

BFS를 떠올리면 상하좌우 노드를 모두 넣고 마지막으로 빼내어 지는 노드의 날짜를 출력하면 된다.

 

 

Queue

- 상하좌우 범위 내에 있고, 해당 노드가 0(방문하지 않음)이면 Queue에 등록

- 등록 후 그래프에 해당 좌표 노드를 1(방문함)로 변경

 

예외처리

- 배열에 0이 남아있다면 모두 익지 못하는 상황이니 -1 출력

 

 

 

  풀이

 

package src.Graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 토마토_7576 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // M: 가로칸 수, N: 세로칸 수
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        // 그래프 배열
        int[][] graph = new int[N][M];

        // BFS
        Queue<int[]> queue = new LinkedList<>();

        // 그래프: 입력
        for(int i = 0; i < N; i++){
            StringTokenizer nodes = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                graph[i][j] = Integer.parseInt(nodes.nextToken());
                if(graph[i][j] == 1){
                    int[] node = {j, i, 0};
                    queue.add(node);
                }
            }
        }


        int day = 0;

        // Solution

        while(!queue.isEmpty()){

            // queue POP()
            int[] node = queue.remove();

            int x = node[0];
            int y = node[1];
            int d = node[2];

            day = Math.max(day, d);

            // queue 등록
            // 상
            if(y - 1 >= 0){
                if(graph[y - 1][x] == 0){
                    graph[y - 1][x] = 1;
                    int[] next = {x, y - 1, d + 1};
                    queue.add(next);
                }
            }
            // 하
            if(y + 1 < graph.length){
                if(graph[y + 1][x] == 0){
                    graph[y + 1][x] = 1;
                    int[] next = {x, y + 1, d + 1};
                    queue.add(next);
                }

            }
            // 좌
            if(x - 1 >= 0){
                if(graph[y][x-1] == 0){
                    graph[y][x - 1] = 1;
                    int[] next = {x - 1, y, d + 1};
                    queue.add(next);
                }

            }
            // 우
            if(x + 1 < graph[y].length){
                if(graph[y][x + 1] == 0){
                    graph[y][x + 1] = 1;
                    int[] next = {x + 1, y, d + 1};
                    queue.add(next);
                }

            }

        }

        // true: 정상, false: 비정상
        boolean result = true;

        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(graph[i][j] == 0){
                    result = false;
                    break;
                }
            }
        }

        if(result){
            System.out.println(day);
        } else {
            System.out.println(-1);
        }



    }
}