[코딩테스트/백준 알고리즘] 7576번 - 토마토 (Java, 자바 풀이)

문제

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

7576번: 토마토

---

문제 설명

---

문제 풀이

 너비 우선 탐색을 활용하면 해결할 수 있는 문제였다.

 이 문제의 풀이에서는 해당 노드를 방문했을 때 몇 다리를 걸쳐서 왔는지 체크해야 했기 때문에 visit을 boolean이 아니라 int형으로 만들어서 값을 업데이트하여 확인했다.

---

코드

import java.util.*;
import java.io.*;

class Main {
    static Queue<int[]> q = new LinkedList<>();
    static int[][] visit = new int[1001][1001];
    static int[][] map = new int[1001][1001];
    static int M;
    static int N;
    static int result = 0;
    static int remain = 0;

    public static void BFS() {
        int[][] point = new int[][] {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        while (!q.isEmpty()) {
            int[] tomato = q.poll();
            remain--;
            for(int[] i : point) {
                int[] newTomato = new int[]{tomato[0] + i[0], tomato[1] + i[1]};
                
                //좌표 유효성 검증
                if (newTomato[0] >= 0 && newTomato[0] < M) {
                    if (newTomato[1] >= 0 && newTomato[1] < N) {
                        
                        //탐색 여부
                        if (visit[newTomato[0]][newTomato[1]] < 0) {
                        
                            //날짜
                            visit[newTomato[0]][newTomato[1]] = visit[tomato[0]][tomato[1]] + 1;	
                            if (visit[newTomato[0]][newTomato[1]] > result)
                                result = visit[newTomato[0]][newTomato[1]];
                            q.offer(newTomato);
                        }
                    }
                }
            }
        }
    }

    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());

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                int tomato = Integer.parseInt(st.nextToken());
                map[j][i] = tomato;

                //익은 토마토
                if(tomato == 1) {
                    q.offer(new int[] {j, i});
                    remain++;
                }

                //안 익은 토마토
                else if (tomato == 0) {
                    visit[j][i] = -1;
                    remain++;
                }

                //빈 칸
                else if (tomato == -1) {
                    visit[j][i] = 1;
                }
            }
        }
        
        //BFS
        BFS();


	//출력
        if(remain == 0)
            System.out.println(result);
        else
            System.out.println(-1);
    }
}