BOJ(백준 온라인 저지) 7576번 with 자바[JAVA]

https://www.acmicpc.net/problem/7576

7576번: 토마토

---

배열로 입력이 들어오고 하나 하나 찾아가는 느낌이 그래프와 BFS 로 풀면 되겠다고 생각했습니다.

 

토마토는 익은 토마토 주변 상하좌우로 안 익은 토마토들을 익게 만드는 것 또한 BFS 라고 생각했습니다.

 

여기에서 문제는

 

• 끝까지 탐색했을 때 모든 토마토가 안 익는 경우가 생기고 이를 어떻게 일반적인 경우와 구분할 것 인지
• 탐색이 끝까지 진행 되었을 때 며칠이 지났는지 어떻게 알 수 있을지

 

였습니다.

 

1. 첫 번째 문제

 

첫 번째의 경우 처음 입력을 받을 때 안 익은 토마토의 개수를 변수로 저장해서

토마토가 익을 때마다, 즉 탐색을 하나 하나 할 때마다 안 익은 토마토의 개수를 차감합니다.

탐색이 모두 끝났을 때 안 익은 토마토의 개수가 0 보다 크다면 이는 모든 토마토가 익지 않은 경우로 -1 을 출력해줍니다.

 

2. 두 번째 문제

 

두 번째의 경우 처음 위치에서 다음 위치로 넘어갈 때 현재 위치에 적혀있는 값 + 1 을 해줍니다.

그렇게 하면 마지막 탐색을 수행한 노드에 적혀있는 값은

토마토가 해당 노드까지 익는데 걸린 시간 + 1 입니다.(* 맨 처음 탐색을 하는 노드가 1로 시작하기 때문에)

따라서 마지막 탐색을 수행하는 노드의 값에 -1 을 해준 값이 출력값이 됩니다.

(* 미로찾기와 비슷)

 

3. 코너 케이스

 

코너 케이스에 대한 생각도 해야합니다.

 

2 2

1 -1

-1 1

 

이 입력되는 경우

탐색은 한 번도 진행되지 않고 그냥 출력은 0 입니다. 따라서 안 익은 토마토의 개수가 0 개 이면 그냥 0 을 출력해줍니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int N;
    public static int M;
    public static int[] dr = {0, 0, 1, -1};
    public static int[] dc = {1, -1, 0, 0};
    public static int unripeTomato = 0;
    public static Queue<int[]> queue = new LinkedList<>();
    public static int[][] farm;

    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());

        farm = new int[M][N];

        for(int i=0; i<M; i++)
        {
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            for(int j=0; j<N; j++)
            {
                int tomato = Integer.parseInt(st2.nextToken());

                farm[i][j] = tomato;

                // 안 익은 토마토의 개수를 세 줍니다.
                if(tomato == 0)
                    unripeTomato++;

                // 익은 토마토의 위치에서 BFS 를 수행해야 하니 1을 발견하면 바로 Queue 에 add 해줍니다.
                if(tomato == 1)
                {
                    int[] startTomato = {i, j};
                    queue.add(startTomato);
                }
            }
        }

        // 익혀야 하는 토마토가 없는 경우 0일입니다.
        if(unripeTomato == 0)
        {
            System.out.println("0");
            return;
        }

        // 익은 토마토가 하나도 없으면 다른 토마토를 익힐 수 없으니 -1을 출력합니다.
        if(queue.isEmpty())
        {
            System.out.println("-1");
            return;
        }

        int result = BFS();

        System.out.println(result);
        return;
    }

    private static int BFS()
    {
        // 마지막으로 탐색했던 토마토의 위치를 저장하기 위한 변수입니다.
        int lastRow = -1;
        int lastCol = -1;

        while(!queue.isEmpty())
        {
            int[] nowPos = queue.poll();
            int nowRow = nowPos[0];
            int nowCol = nowPos[1];

            for(int i=0; i<4; i++)
            {
                int nextRow = nowRow + dr[i];
                int nextCol = nowCol + dc[i];

                if(nextRow < 0 || nextRow >= M || nextCol < 0 || nextCol >= N)
                    continue;

                if(farm[nextRow][nextCol] != 0)
                    continue;

                // 현재 토마토의 값 + 1 을 다음 탐색하는 노드의 값으로 넣어줍니다.
                farm[nextRow][nextCol] = farm[nowRow][nowCol] + 1;
                int[] nextPos = {nextRow, nextCol};
                queue.add(nextPos);

                // 탐색을 할 때 마다 안 익은 토마토의 개수를 줄여줍니다.
                unripeTomato--;

                lastRow = nextRow;
                lastCol = nextCol;
            }
        }

        // 모든 탐색이 끝났어도 안 익은 토마토가 있다면 -1 을 출력합니다.
        if(unripeTomato != 0)
            return -1;

        // 마지막으로 탐색했던 노드의 값 -1 을 return 해 줍니다.
        return farm[lastRow][lastCol] - 1;
    }
}

---

• 느낀 점

최단 어쩌고는 BFS 이다.