[BFS] 백준 - 5558번: チーズ (Cheese) Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

5558번: チーズ (Cheese)

 

 

문제는 다음과 같다. 처음에 N * M 사이즈의 맵이 주어지고 최대 치즈의 단단함이 주어진다.

 

생쥐는 처음에 체력이 1인데 치즈를 먹을수록 체력은 올라간다.

하지만 치즈가 단단하기 때문에 같거나 덜 단단한 치즈만 먹을 수 있다.

즉, 체력 1일 때는 1의 치즈, 체력 3일 땐 1, 2, 3의 치즈만 먹을 수 있다.

 

그렇게 해서 치즈를 다 먹을 때까지 몇 분이 걸리는지 표시하면 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[][] map;
    static int n;
    static int m;
    static int h;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        map = new int[n][m];

        int startX = 0, startY = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j = 0; j < m; j++) {
                if (str.charAt(j) == 'S') {
                    startX = i;
                    startY = j;
                    map[i][j] = 11; //치즈 경도는 최대 9이기 때문에 생쥐는 11로 표시
                } else if (str.charAt(j) == '.') {
                    map[i][j] = 0; //빈 공간은 0
                } else if (str.charAt(j) == 'X') {
                    map[i][j] = -1; //벽은 -1
                } else {
                    map[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
                }
            }
        }

        bfs(startX, startY);
    }

    private static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y, 0, map[x][y] - 10});
        boolean[][] visit = new boolean[n][m];

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int xx = poll[0]; //x좌표
            int yy = poll[1]; //y좌표
            int cc = poll[2]; //분 카운트
            int hh = poll[3]; //생쥐 크기

            if (hh > h) {
                //현재 생쥐의 크기가 최대 치즈 경도보다 큰 경우 종료
                System.out.println(cc);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nowX = xx + dx[i];
                int nowY = yy + dy[i];

                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                    if (map[nowX][nowY] > 0 && map[nowX][nowY] <= hh) {
                        //치즈를 먹었을 때는 visit과 q를 비워주고 다시 그 지점부터 시작해야 한다.
                        q.clear();
                        q.add(new int[]{nowX, nowY, cc + 1, hh + 1});
                        map[nowX][nowY] = 0;
                        visit = new boolean[n][m];
                        break;
                    } else if (map[nowX][nowY] >= 0 && !visit[nowX][nowY]) {
                        q.add(new int[]{nowX, nowY, cc + 1, hh});
                        visit[nowX][nowY] = true;
                    }
                }
            }
        }
    }
}