자바(백준) 7576 토마토-2차원(2021.05.22 수정)

package BFS;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int M,N;
    static int ad[][];
    static boolean visit[][];
    static int count = 0;
    static Queue<Po> q = new LinkedList<>();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        ad = new int[N+1][M+1];
        visit = new boolean[N+1][M+1];
 
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= M; j++){
                ad[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(ad[i][j] == 1 && !visit[i][j]){
                    q.offer(new Po(i,j,0));
                    visit[i][j] = true;
                }
            }
        }
 
        bfs();
 
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(ad[i][j] == 0){
                    System.out.println(-1);
                    return;
                }
            }
        }
 
        System.out.println(count);
    }
 
    static void bfs(){
        int dx[] = {-1,1,0,0};
        int dy[] = {0,0,1,-1};
        while(!q.isEmpty()){
            Po p1 = q.poll();
            count = Math.max(count, p1.depth);
            for(int i = 0; i < 4; i++){
                int rex = p1.x + dx[i];
                int rey = p1.y + dy[i];
                if(isRangeTrue(rex,rey) && ad[rex][rey] == 0 && !visit[rex][rey]){
                    q.offer(new Po(rex,rey,p1.depth+1));
                    visit[rex][rey] = true;
                    ad[rex][rey] = 1;
                }
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y){
        return x > 0 && x <= N && y > 0 && y <= M;
    }
}
 
class Po{
    int x, y, depth;
 
    public Po(int x, int y, int depth){
        this.x = x;
        this.y = y;
        this.depth = depth;
    }
}
 

토마토 3차원을 풀고 나니 이 문제는 쉽게 느껴졌다. 하지만 처음에는 큐를 static으로 선언하지 않고, bfs 메소드 안에 선언했다. 그러더니 한 케이스의 답이 나오질 않았다. 그래서 보니, 나는 for문을 이용하여 순차적으로 bfs를 대입하고 있던 것이다. 

그래서 예제3을 돌려보면 정답이 9가 나온다. 왜냐하면 나는 처음 1만 넣고 bfs를 돌리고, 또, 마지막 1에 bfs를 돌렸기 때문이다. 하지만 처음 1과 마지막 1이 같이 bfs가 돌아야 한다. 그래서 큐를 static 선언하여, ad배열에 숫자를 집어넣을 때, 1인 index를 바로 큐에 poll 하였다. 그래서 다양한 문제가 있는 것을 깨닫고, 어디에는 큐를 static으로 선언해서 한 번에 하는지, 아니면 순차적으로 돌려도 되는지 유형별로 생각할 필요가 있는 것 같다.

 

---

2021.05.22 두 번째 풀이

 

오답 노트 & 새로 알게 된 점

이 문제를 저번에 풀어본 적이 있어서 다시 푸는데 어려움은 없었다. 아마 다른 점은 인접 행렬을 구현할 때, 최대 크기 + 1로 해주었냐 이 차이인 것 같다. 복기하자면, bfs에서 최단경로를 구할 때에는 x, y좌표를 나타내는 class에서 count변수도 같이 추가해주면 좋다. 하지만 이 문제를 처음에 생각하면서 시간 복잡도를 생각해보았다. 인접 행렬을 이용하여 구현한 bfs는 O(n * m)이다. 그러나 여기서 bfs로 구현한 뒤, arr 값에 0이 있는지 없는지 탐색을 해야 한다. 그래서 O(n * m)이 된다. 따라서, TLE가 날 줄 알았는데 나지 않았다. 아마 for문 안에서 한 번에 돌리지 않고 따로 돌려서 그런 것 같다.

 

코드

package BFS;
 
import java.io.*;
import java.util.*;
 
public class Main{
    static int arr[][];
    static boolean visit[][];
    static int row, col;
    static Queue<TomatoPoint> q = new ArrayDeque<>();
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        //입력 --> 여기서 row col을 반대로 줌
        col = Integer.parseInt(st.nextToken());
        row = Integer.parseInt(st.nextToken());
 
        //상하좌우 이동
        int dx[] = {-1,1,0,0};
        int dy[] = {0,0,1,-1};
        int cnt = 0;
 
        //배열 객체 생성
        arr = new int[row][col];
        visit = new boolean[row][col];
 
        for(int i = 0; i < row; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < col; j++){
                int num = Integer.parseInt(st.nextToken());
                arr[i][j] = num;
                if(num == 1)
                    //아마 처음에 큐에 넣으니까 1부터 시작해야할듯
                    //동시에 토마토가 익으니까 큐에 바로 집어넣어줌
                    q.offer(new TomatoPoint(i, j, 1));
            }
        }
 
        //인접 행렬로 해서 시간복잡도 O(nm)
        while(!q.isEmpty()){
            TomatoPoint tp = q.poll();
            visit[tp.x][tp.y] = true;
            for(int i = 0; i < 4; i++){
                int X = tp.x + dx[i];
                int Y = tp.y + dy[i];
                if(isRangeTrue(X, Y) && !visit[X][Y] && arr[X][Y] == 0){
                    q.offer(new TomatoPoint(X, Y, tp.count + 1));
                    visit[X][Y] = true;
                    arr[X][Y] = 1;
                    //cnt 구하는 방법이 생각이 안남. 그래서 이거라도 했음. 다른 방법 찾아봐야겠다.
                    cnt = Math.max(cnt, tp.count);
                }
            }
        }
 
        //여기서 탐색 O(nm)
        for(int index1[] : arr){
            for(int index2 : index1){
                if(index2 == 0){
                    System.out.println(-1);
                    System.exit(0);
                }
            }
        }
 
        System.out.println(cnt);
    }
 
    static boolean isRangeTrue(int x, int y){
        return x >= 0 && x < row && y >= 0 && y < col;
    }
}
 
class TomatoPoint{
    int x, y, count;
    TomatoPoint(int x, int y, int count){
        this.x = x;
        this.y = y;
        this.count = count;
    }
}