[PS] BOJ7576 토마토 ( BFS ) with JAVA

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

7576번: 토마토

 

◎ 문제풀이

 

토마토가 익는 비용이 하루로 고정되어 있고 상하좌우로 이동가능하고 최소일수 즉, 최단거리를 구하는 문제이니 BFS 알고리즘이 떠올랐다. 그래서 BFS 알고리즘으로 풀었는데 시간초과가 발생했다.  돌이켜 생각해보니 나는 BFS를 가장한 DFS 풀이를 한거였다.

 

1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

 

익어있는 토마토는 2개이다. (0,0)와 (5,3)이다. 

 

난 (0.0)부터 BFS를 시작하고 (0.0)이 끝나면 (5,3)의 BFS를 따로 시작했다. 이는 BFS를 사용했지만 사실상 깊이우선탐색(DFS)이다. DFS는 최악의 경우도 고려하기 때문에 최단거리를 구할 수는 있지만 시간이 오래 걸린다. 그러므로 (0.0)과 (5,3)을 큐에 넣고 한 회차씩 번갈아가면서 탐색해야 한다. 토마토가 0인 경우에만 탐색할 수 있고 0이 아니면 누군가가 먼저 토마토를 익혔다고 판단하고 다른 길을 탐색한다.

 

 

◎ 코드

import java.io.*;
import java.util.*;
import static java.lang.Math.max;

//BOJ7576 토마토
public class Bfs1 {

    static Queue<int[]> queue = new LinkedList<>();
    static StringTokenizer st;
    static int[][] box;
    static int n;
    static int m;

    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};

    // 시간초과가 난 이유는 BFS로 풀었는데 결국은 DFS가 되었기 때문이다.
    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        box = new int[n][m];

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

    public static void solution(){
        bfs(queue);
        System.out.println(getResult());
    }

    public static void bfs(Queue<int[]> queue){
        while(!queue.isEmpty()){
            int[] pos = queue.remove();
            int y = pos[0];
            int x = pos[1];

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

                if(isValidate(nx,ny) && box[ny][nx] == 0){
                    box[ny][nx] = box[y][x]+1;
                    int[] nextPos = {ny,nx};
                    queue.add(nextPos);
                }
            }
        }
    }

    public static boolean isValidate(int x, int y){
        if( x>=0 && y>=0 && x < m && y < n ) return true;
        else return false;
    }

    public static int getResult(){
        int maxValue = 1;
        for(int i =0; i<n;i++){
            for(int j =0;j<m;j++){
                if(box[i][j] == -1) continue;
                if(box[i][j] == 0) return -1;
                maxValue = max(maxValue,box[i][j]);
            }
        }
        if(maxValue == 1) return 0;
        else return maxValue -1;
    }
}