백준 7576번 ) 토마토 (java)

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

7576번: 토마토

 

문제

 

풀이

익은 토마토를 배열에 입력하면서, 큐에 동시에 집어넣는다.

BFS 함수를 호출하면서 큐에서 토마토들을 꺼내며 x, y 축으로 하나씩 이동하여 익은토마토인지 아닌지 확인하며 날짜를 더해나간다.

만약에 이미 익었으면 따로 체크하지 않고, 토마토가 0 즉 익지 않은 경우에만 그 옆의 토마토가 익은 날짜에 +1 을 한다.

 

마지막으로 모든 배열을 돌아가면서 확인하여 토마토가 최종으로 익은 날짜를 확인하여 max로 반환한다.

토마토가 처음 익은 날이 1이므로, 결과는 -1 하여 반환한다.

 

코드

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

class tomato {
    int x;
    int y;

    tomato(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class BOJ_7576 {
    static int[][] tomatoes;
    static Queue<tomato> q;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        tomatoes = new int[n][m];
        q = new LinkedList<tomato>();

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<m; j++){
                tomatoes[i][j] = Integer.parseInt(st.nextToken());
                if(tomatoes[i][j] == 1) q.add(new tomato(i,j));
            }
        }

        System.out.println(bfs(n,m));

    }
    
    public static int bfs(int n, int m){
        while(!q.isEmpty()){
            tomato t = q.poll();
            int x = t.x;
            int y = t.y;

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

                if( nextX >= 0 &&  nextY>=0 && nextX<n && nextY<m && tomatoes[nextX][nextY] == 0){
                    q.add(new tomato(nextX, nextY));
                    tomatoes[nextX][nextY] = tomatoes[x][y] + 1;
                }
            }
        }

        int day = Integer.MIN_VALUE;

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(tomatoes[i][j] == 0) return -1;
                day = Math.max(day, tomatoes[i][j]);
            }
        }

        return (day-1);
    }
}

기억할 점

전형적인 BFS 문제이다. BFS 문제는 옆으로 퍼져나가는 것을 확인하는 문제이고, dx, dy 를 각각 정하고 4만큼 반복하여 위아래 양옆 값을 확인한다.

• 지난번에는 좌표를 배열로 저장하여, 큐에 직접 int[] 를 넣었는데 이번에는 클래스를 따로 선언했다. new tomato 만 하면 되니까 훨씬 편하다. (배열 사용시 배열을 매번 생성해주어야 했다.)
• 여러번 적는 것이지만, queue 사용 시, add 는 예외를 발생시키고 offer 는 null false를 반환해준다. peek 는 값을 읽어오기만하며, poll 은 값을 읽어오는 동시에 큐에서 제거한다.
  •  이 때, remove와 poll 의 차이는 remove 실패 시 예외 발생, poll 실패시 null 을 반환한다.
  •  

• 정수 최소값 지정시에는 Integer.MIN_VALUE; 를 사용한다. (최댓값의 경우에는 MAX)
• 최댓값 비교하는 함수는 간단히 Math.max( a, b ) 를 사용하자!

 

이 문제는 다시 한번 복습해도 좋을 것 같다.