백준 7576번 : 토마토

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

7576번: 토마토

풀이과정

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.IOException;
 
public class Main {
    public static void main(String args[]) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        int[][] tomato = new int[H][W];

        for(int i=0; i<H; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<W; j++) {
                tomato[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //end input
		
        Queue<int[]> que= new LinkedList<>(); //다음 위치 저장을 위한 queue
        boolean[][] visited = new boolean[H][W]; //방문체크용 배열
        
        int[] dirX = new int[] {-1,1,0,0}; //주변탐색을 위한 배열
        int[] dirY = new int[] {0,0,-1,1};
        
        //처음 주어진 토마토가 있는 위치를 que에 저장해준다.
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
            
                if(tomato[i][j]>0) {
                    que.offer(new int[] {i,j});
                    visited[i][j] = true;
                }
                
            }//end j for 
        }//end i for

	//주어진 토마토가 있는 위치부터 BFS시작
        while(!que.isEmpty()) {
            int[] location = que.poll();
            int nowX = location[0];
            int nowY = location[1];

            for(int k=0; k<4; k++) {
                int nextX = nowX+dirX[k];
                int nextY = nowY+dirY[k];

                if(nextX<0 || nextY<0 || nextX>=H || nextY>=W) {
                    continue;
                }
                
		//만약 토마토 주위에 토마토가 있고, 처음 방문하는 곳이라면,
                if(tomato[nextX][nextY]>=0 && visited[nextX][nextY]!=true) {
                    que.offer(new int[] {nextX,nextY}); //que에 토마토 위치 저장
                    visited[nextX][nextY] = true; //방문체크
                    tomato[nextX][nextY] = tomato[nowX][nowY]+1; //토마토가 며칠만에 익었는지 확인
                }

            }//end k for
        }//end while

	//가장 늦게 익은 토마토 확인 & 안익은 토마토가 있는지 확인
        boolean check = false;
        int max = 0;

        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                if(tomato[i][j]==0) {
                    check = true;
                }
                if(tomato[i][j] > max) max = tomato[i][j];
            }

        }
        if(check==true) {
            System.out.println(-1);
        }
        else {
            System.out.println(max-1); //0부터 시작하지 않고 1부터 시작했기 때문에 -1해줌
        }

    }//end Main	
}

처음 문제를 봤을 때는 왠지 queue를 쓰지않고 순회로만 풀 수 있을 것 같아서 쓰지 않고 풀어보려고 했는데, 실패했다...

딴 사람들 풀이를 살~짝 참고해봤더니 다들 queue는 사용하길래 queue를 써야겠다 싶었다.

요즘 BFS문제만 계속 풀고 있는데, 계속 풀다보니까 어느정도 감이 잡히는 것 같다.