자바(Java) 알고리즘 문제풀이 토마토 [인프런 / BFS]

출처) 인프런

강의의 문제를 가져왔기 때문에 밝힙니다 ! 
임의로 추가, 수정, 삭제한 내용들이 있으니 정확한 이해를 위해서는 강의를 구매하시는 것을 추천드립니다 😅
출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 (인프런 강의) 

 

 

---

 

 

풀이 코드

BFS 활용문제로, 토마토가 다 익는데 최소 몇일이 걸리는지 구하는 문제이다.

익은 토마토 기준으로 퍼져나가면서 주위의 토마토가 익는데, 최초에 익은 토마토가 한 개가 아니기 때문에 BFS 함수 호출  전, 미리 큐에

익은 토마토의 좌표를 넣어줘야 한다. 이 때문에 큐를 static 변수로 선언.

그러고 방향 벡터에서 상,하,좌,우 로 익지 않은 토마토를 발견하면 이동하면서 익은 토마토로 변경하고 익는데 걸리는 날짜를 좌표로 표현한 dis[][] 배열의 똑같은 좌표에도 이전 값에서 1을 더해준 값을 넣어준다. 그리고 다시 큐에 이동한 좌표를 넣어주고 반복하면 끝.

 

다시 이중 반복문으로 map[][] 에 0인 값이 있다면 모든 토마토가 익지 못했으므로 -1 를 출력하고 바로 return 하도록 했고 그게 아니라면

Math.max() 함수를 사용해 count 에 dis 배열의 가장 큰 값을 담아주고 출력해주도록 했다.

package backjoonsliver.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;

class Point2 {
    int x;
    int y;

    public Point2(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class 토마토 {
    static int n;
    static int m;
    static int count;
    static int answer;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] map;
    static int[][] dis;
    static Queue<Point2> 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());
        map = new int[n][m];
        dis = new int[n][m];

        // 1. 최초 맵 생성
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 2. 익은 토마토 찾아서 Queue 에 미리 삽입
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1) {
                    q.offer(new Point2(i, j));
                }

            }
        }

        BFS();

        for (int i=0; i<n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1);
                    return;
                } else {
                    count = Math.max(count, dis[i][j]);
                }
            }
        }
        System.out.println(count);
    }

    private static void BFS() {
        while (!q.isEmpty()) {
            Point2 tmp = q.poll();

            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + tmp.x;
                int ny = dy[i] + tmp.y;

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] == 0) {
                    map[nx][ny] = 1; // 체크 표시 (익은걸로 표시)
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                    q.offer(new Point2(nx, ny));
                }
            }
        }
    }
}