[백준-7576]-[BFS]-토마토

문제 링크 : https://www.acmicpc.net/problem/7576

이 문제는 당연히 BFS 로 풀어야 하는 문제다. 

하지만 생각을 제대로 하지 못하면 어리석은 소스로 시간 초과에 걸리는 상황을 만들 수 있다. 

먼저 어리석은 생각으로 한 코딩을 올리면서 한번의 반성을 하고 시간 초과를 해결한 소스를 올리면서 다시 반성해야겠다. 

일단 아주 쉽게 아 BFS로 안익은 토마토 카운트가 0일 될때까지 BFS를 돌리면서 한칸씩 익히면 되겠구나! 이 생각을 아주 엇나가게 했다. 

내가 한 잘못된 생각은 이렇다.

시간초과 소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static int[][] tomatoBox;
    public static int ROW;
    public static int COL;
    
    
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        COL = Integer.parseInt(st.nextToken());
        ROW = Integer.parseInt(st.nextToken());
        
        tomatoBox = new int[ROW][COL];
        
        
        
        int cnt = 0;
        int time = 0;
        
        for(int i = 0; i < ROW; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < COL; j++) {
                tomatoBox[i][j] = Integer.parseInt(st.nextToken());
                if(tomatoBox[i][j] == 0) cnt++;
            }
        }
        
        int prevCnt = cnt;
        while(cnt > 0) {
            boolean[][] visited = new boolean[ROW][COL];
            
            for(int i=0; i < ROW; i++) {
                for(int j=0; j < COL; j++) {
                    if(tomatoBox[i][j] == 1 && !visited[i][j]) cnt = BFS(i, j, visited, cnt);
                }
            }
            
            if(cnt != 0 && prevCnt == cnt) {
                time = -1;
                break;
            }
            time += 1;
            prevCnt = cnt;
        }
        System.out.println(time);
    }
    
    public static int BFS(int row, int col, boolean[][] visited, int cnt) {
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] {row, col});
        
        while(!queue.isEmpty()) {
            row = queue.peek()[0];
            col = queue.peek()[1];
            queue.poll();
            
            if(row < 0 || col < 0 || row >= ROW || col >= COL) continue;
            if(tomatoBox[row][col] == -1) continue;
            if(visited[row][col]) continue;
 
            visited[row][col] = true;
            
            // 1이면 익혀라
            if(tomatoBox[row][col] == 1) {
                queue.offer(new int[] {row-1, col});
                queue.offer(new int[] {row, col-1});
                queue.offer(new int[] {row+1, col});
                queue.offer(new int[] {row, col+1});
            }else if(tomatoBox[row][col] == 0){
                // 0이면 익어라
                tomatoBox[row][col] = 1;
                cnt -= 1;
            }
        }
        return cnt;
    }
 
}

38번째줄 안익은 토마토의 수가 0이상일 동안 while을 돌면서 그리고 이중 for문을 돌면서 아직 방문하지 않은 익은 토마토들을 BFS를 돌면서 주변 안익은 토마토를 익히는 소스를 작성했다.

한번 BFS를 돌았을때는 안익은 토마토의 수를 비교하고 BFS 돌기전의 수와 같으면 -1을 출력하게 작성하였다.

이렇게 소스를 짜니 아주 간단하게 아슬아슬하지도 않게 너무나 당연하게 시간초과가 발생했다. 

내 수준의 현실을 보았고 반성하며 소스를 다 지우고 다시한번 생각을 해봤다.

굳이 안익은 토마토가 0이 될때까지 while 반복문을 사용할 필요가 없다는것을 느꼈다.

처음 토마토 정보를 입력받을때 익은 토마토의 정보를 먼저 queue에 삽입하고 이것들로 BFS를 돌리면 되는거였다. 

이것들 주변의 있는 안익은 토마토들이 익는다면 하루가 지난거고 또 이 토마토들 주변의 안익은 토마토들이 익는다면 이틀이 지난거고.. 

생각해보면 아주 간단한 BFS 였는데 너무 생각을 복잡하게 했던거 같다. 

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
        
    COL = Integer.parseInt(st.nextToken());
    ROW = Integer.parseInt(st.nextToken());
    queue = new LinkedList<int[]>();
        
    tomatoBox = new int[ROW][COL];
        
    for(int i=0; i < ROW; i++) {
        st = new StringTokenizer(br.readLine());
        for(int j=0; j < COL; j++) {
            tomatoBox[i][j] = Integer.parseInt(st.nextToken());
            
            if(tomatoBox[i][j] == 1) queue.offer(new int[] {i, j, 0});
            else if(tomatoBox[i][j] == 0) COUNT += 1;
        }
    }
    
    BFS();
    System.out.println(COUNT > 0 ? -1 : MAX);
}

16번째 17번째 줄을 보게 되면 익은 토마토면 queue에 삽입했다. 정수형 배열로 큐에 삽입했고 {행 좌표, 열 좌표, 일자} 로 구성했다.

처음 입력 될때는 당연히 일자는 0일이니깐 초기 값으로 0을 지정했다.

그리고 안익은 토마토들의 수를 계산했다. 안익은 토마토가 익어갈때 저 카운트를 같이 하나씩 감소시킨다.

나중에 결과를 출력할때 아직 카운트가 0 이상이면 아직 덜 익었다는 것이고 -1을 출력하면 된다.

public static void BFS() {
    boolean[][] visited = new boolean[ROW][COL];
    while(!queue.isEmpty()) {
        int currY = queue.peek()[0];
        int currX = queue.peek()[1];
        int days = queue.peek()[2];
            
        queue.poll();
        // 좌표 범위를 벗어나는지 유효성 체크
        if(currY < 0 || currX < 0 || currY >= ROW || currX >= COL) continue;
 
        // 익은 토마토가 아닌 것들은 안익은 토마토를 익힐 수 없다.
        if(tomatoBox[currY][currX] != 1) continue;
        
        // 익은 토마토라도 한번 익힌 토마토는 이미 주변을 익혀버린 전력이 있기에 다시 익힐 수 없다.
        if(visited[currY][currX]) continue;
        // 방문 여부 값을 변경해준다
        visited[currY][currX] = true;
        // 본인의 차수가 max보다 크면 max 값을 변경한다.
        if(MAX < days) MAX = days;
            
        // 주변에 안익은 토마토들을 익히고 큐에 삽입해 준다. 상,하,좌,우
        // 큐에 삽입할때 days에 1을 더한다.
            
        // 상 토마토가 안익었나
        if(currY > 0 && tomatoBox[currY-1][currX] == 0) {
            queue.offer(new int[] {currY-1, currX, days+1});
            tomatoBox[currY-1][currX] = 1;
            COUNT -= 1;
        }
        // 하 토마토가 안익었나
        if(currY < ROW-1 && tomatoBox[currY+1][currX] == 0) {
            queue.offer(new int[] {currY+1, currX, days+1});
            tomatoBox[currY+1][currX] = 1;
            COUNT -= 1;
        }
        // 좌 토마토가 안익었나
        if(currX > 0 && tomatoBox[currY][currX-1] == 0) {
            queue.offer(new int[] {currY, currX-1, days+1});
            tomatoBox[currY][currX-1] = 1;
            COUNT -= 1;
        }
        // 우 토마토가 안익었나
        if(currX < COL-1 && tomatoBox[currY][currX+1] == 0) {
            queue.offer(new int[] {currY, currX+1, days+1});
            tomatoBox[currY][currX+1] = 1;
            COUNT -= 1;
        }
    }
}

이제 BFS로 안익은 토마토들을 익혀버렸다.

queue에는 무조건 익은 토마토들이 있고 각 토마토의 일자가 MAX 값보다 크면 MAX 값을 변경시켰다. 

익은 토마토 기준 안익은 토마토가 있으면 일자는 증가 시키고 안익은 토마토 수는 감소 시켰다. 

상, 하, 좌, 우 안의 소스는 다 비슷한 소스라 공통으로 쓸수 있겠지만 안했다.

이렇게 소스를 작성하고 제출하니 바로 통과가 됐다.

좀더 깊은 생각으로 문제를 풀어야겠다는 반성을 다시 하며 전체소스로 마무리를 한다.

전체소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static int[][] tomatoBox;
    public static int ROW;
    public static int COL;
    
    public static Queue<int[]> queue;
    
    public static int MAX = Integer.MIN_VALUE;
    public static int COUNT = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        COL = Integer.parseInt(st.nextToken());
        ROW = Integer.parseInt(st.nextToken());
        queue = new LinkedList<int[]>();
        
        tomatoBox = new int[ROW][COL];
        
        for(int i=0; i < ROW; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < COL; j++) {
                tomatoBox[i][j] = Integer.parseInt(st.nextToken());
                
                if(tomatoBox[i][j] == 1) queue.offer(new int[] {i, j, 0});
                else if(tomatoBox[i][j] == 0) COUNT += 1;
            }
        }
        
        BFS();
        System.out.println(COUNT > 0 ? -1 : MAX);
    }
    
    public static void BFS() {
        boolean[][] visited = new boolean[ROW][COL];
        while(!queue.isEmpty()) {
            int currY = queue.peek()[0];
            int currX = queue.peek()[1];
            int days = queue.peek()[2];
            
            queue.poll();
            // 좌표 범위를 벗어나는지 유효성 체크
            if(currY < 0 || currX < 0 || currY >= ROW || currX >= COL) continue;
 
            // 익은 토마토가 아닌 것들은 안익은 토마토를 익힐 수 없다.
            if(tomatoBox[currY][currX] != 1) continue;
            
            // 익은 토마토라도 한번 익힌 토마토는 이미 주변을 익혀버린 전력이 있기에 다시 익힐 수 없다.
            if(visited[currY][currX]) continue;
            // 방문 여부 값을 변경해준다
            visited[currY][currX] = true;
            // 본인의 차수가 max보다 크면 max 값을 변경한다.
            if(MAX < days) MAX = days;
            
            // 주변에 안익은 토마토들을 익히고 큐에 삽입해 준다. 상,하,좌,우
            // 큐에 삽입할때 days에 1을 더한다.
            
            // 상 토마토가 안익었나
            if(currY > 0 && tomatoBox[currY-1][currX] == 0) {
                queue.offer(new int[] {currY-1, currX, days+1});
                tomatoBox[currY-1][currX] = 1;
                COUNT -= 1;
            }
            // 하 토마토가 안익었나
            if(currY < ROW-1 && tomatoBox[currY+1][currX] == 0) {
                queue.offer(new int[] {currY+1, currX, days+1});
                tomatoBox[currY+1][currX] = 1;
                COUNT -= 1;
            }
            // 좌 토마토가 안익었나
            if(currX > 0 && tomatoBox[currY][currX-1] == 0) {
                queue.offer(new int[] {currY, currX-1, days+1});
                tomatoBox[currY][currX-1] = 1;
                COUNT -= 1;
            }
            // 우 토마토가 안익었나
            if(currX < COL-1 && tomatoBox[currY][currX+1] == 0) {
                queue.offer(new int[] {currY, currX+1, days+1});
                tomatoBox[currY][currX+1] = 1;
                COUNT -= 1;
            }
        }
    }
 
}