백준7576 토마토 (자바)

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

7576번: 토마토

BFS를 응용하는 문제였다. 처음에 토마토가 다익었는지 확인하기 위해 이차원 배열을 다 탐색하여서 문제를 풀었는데 시간초과가 떠서 시간복잡도에 생각을 하다보니 계속 while문을 돌때마다 n*m번 탐색하는 것은 비효율적이라는 것을 알게 되어 처음에 입력 받을 때 익혀야 할 토마토 즉0이 몇개인지 개수를 세어 1로 바꿀때마다 하나 씩 빼주는 방식을 이용해서 문제를 풀었다. 간단한 개념 같지만 실제로 코딩테스트나 시험문제를 풀 때 큰 도움이 될 것 같다. 

 

 

 

package DFS_BFS;
 
import java.io.*;
import java.util.*;
 
class P {
    int y, x, hop;
 
    P(int y, int x, int hop) {
        this.y = y;
        this.x = x;
        this.hop = hop;
    }
}
 
public class 토마토 {
    public static void main(String[] args) throws Exception {
        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());
        int[][] maze = new int[n][m];
        int cntZero = 0;
        ArrayList<P> tomato = new ArrayList<P>();
        boolean[][] visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(st.nextToken());
                if (maze[i][j] == 1) tomato.add(new P(i, j, 1));
                else if(maze[i][j]==0) cntZero++;
            }
        }
        int ans = BFS(maze, visit, tomato,cntZero);
        System.out.println(ans);
    }
 
    static int BFS(int[][] maze, boolean[][] visit, ArrayList<P> tomato,int cntZero) {
        int ans = Integer.MAX_VALUE;
        Queue<P> q = new LinkedList<>();
 
        for (P point : tomato) {
            q.add(point);
        }
        if (cntZero==0) return 0;
 
        while (!q.isEmpty()) {
            P p = q.poll();
            visit[p.y][p.x] = true;
 
            if (p.y + 1 < maze.length && !visit[p.y + 1][p.x] && maze[p.y + 1][p.x] == 0) {
                visit[p.y + 1][p.x] = true;
                cntZero--;
                maze[p.y + 1][p.x] = 1;
                q.add(new P(p.y + 1, p.x, p.hop + 1));
            }
            if (p.y - 1 >= 0 && !visit[p.y - 1][p.x] && maze[p.y - 1][p.x] == 0) {
                visit[p.y - 1][p.x] = true;
                cntZero--;
                maze[p.y - 1][p.x] = 1;
                q.add(new P(p.y - 1, p.x, p.hop + 1));
            }
            if (p.x + 1 < maze[0].length && !visit[p.y][p.x + 1] && maze[p.y][p.x + 1] == 0) {
                visit[p.y][p.x + 1] = true;
                cntZero--;
                maze[p.y][p.x + 1] = 1;
                q.add(new P(p.y, p.x + 1, p.hop + 1));
            }
            if (p.x - 1 >= 0 && !visit[p.y][p.x - 1] && maze[p.y][p.x - 1] == 0) {
                visit[p.y][p.x - 1] = true;
                cntZero--;
                maze[p.y][p.x - 1] = 1;
                q.add(new P(p.y, p.x - 1, p.hop + 1));
            }
 
            if (cntZero==0) return p.hop;
 
        }
        return -1;
 
 
    }
 
}