[백준] 7576 : 토마토 (JAVA)

문제

BOJ 7576 : 토마토 - https://www.acmicpc.net/problem/7576

풀이

익은 토마토를 기준으로 주변 안익은 토마토들이 익어간다. 한 위치를 기준으로, 주변 위치들이 영향을 받기 때문에 우선 BFS로 풀이해야겠다고 생각했다.

입력받을 시 안익은 토마토의 개수를 세고, 익은 토마토 정보는 Queue에 넣어둔다.

다만 한 위치에서만 퍼지는 게 아니라, 익은 토마토가 여러 개라면 여러 개를 기준으로 각각의 위치에서 퍼지기 때문에 각각의 토마토가 자신이 언제 익었는지에 대한 정보를 갖고 있을 수 있도록 위치 class를 따로 정의해서 구현했다.

안익은 토마토가 익은 토마토에게 영향을 받게 되어 익게 되면, 입력 시 세어두었던 안익은 토마토의 개수(tomato_not)를 -1 해주었다(토마토가 전부 익었는지 확인하기 위해). 또한 최대 며칠이 걸렸는지만 확인하면 되기 때문에, day를 업데이트 해주었다.

더 이상 토마토를 익게할 수 없을 때(==queue가 비었을 때), 안익은 토마토가 없다면 day를 출력하고, 있다면 -1을 출력한다.

코드

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

public class Main {

    static class Loc{
        int i;
        int j;
        int day;

        public Loc(int i, int j, int day) {
            this.i = i;
            this.j = j;
            this.day = day;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int m = Integer.parseInt(inputs[0]);
        int n = Integer.parseInt(inputs[1]);

        int[][] map = new int[n][m];
        Queue<Loc> queue = new LinkedList<>();

        int tomato_not = 0;
        for (int i = 0; i < n; i++) {
            inputs = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(inputs[j]);
                
                if(map[i][j]==0) tomato_not++; 	// 안익은 토마토 수 카운트

                if(map[i][j]==1){		// 익은 토마토는 큐에 넣기
                    queue.add(new Loc(i, j, 0));
                }
            }
        }

        int day = 0;

	// 움직일 4방향
        int[] mi = {0, 0, -1, 1};
        int[] mj = {1, -1, 0, 0};

        while (!queue.isEmpty()) {
            Loc now = queue.poll();

            for (int d = 0; d < 4; d++) {
                int ni = now.i + mi[d];
                int nj = now.j + mj[d];

                if(ni<0 || ni>=n || nj<0 || nj>=m) continue;
                
                if(map[ni][nj] == 0){ // 주변에 안익은 토마토가 있으면
                    map[ni][nj] = 1; 
                    tomato_not --;
                    queue.add(new Loc(ni, nj, now.day+1));
                    day = Math.max(day, now.day+1); // 날짜 업데이트
                }
            }
        }

        if(tomato_not==0){
            System.out.println(day);
        }else{
            System.out.println(-1);
        }
    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 너비 우선 탐색
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

• 뭔가 퍼져나간다! 하면 BFS를 생각할 것. 한 위치에서만 퍼지는 게 아니고 익은 토마토가 여러 개면 여러 개를 기준으로 퍼져나가기 때문에 날짜 카운트 처리를 어떻게 해야할 지 조금 고민했다(Queue를 2개 만들어야하나,,, day저장할 배열을 만들어야하나 고민,,,). 어쨌든 최대 며칠이 걸렸는지만 확인하면 되기 때문에 각각의 토마토가 '언제 익었는지'에만 집중하면 됐다!

참고 사이트

딱히 없음