BOJ_1600 : 말이 되고픈 원숭이

👉 문제링크

1600번: 말이 되고픈 원숭이

---

---

🔸 문제 분석 🔸

• H x W 격자 판에서 왼쪽 위 끝 부터 오른쪽 아래 끝 까지 가는 동작의 최소값을 출력한다.
  • 원숭이의 움직임 : 인접 4칸으로 이동 가능
  • 말의 움직임 : k번 만큼 이동 가능
• BFS로 2가지 풀이를 할 수 있다.
  1. 말 이동 횟수를 적게 쓸 수록 좋다.(그리디)
  2. 3중 배열로 방문을 체크한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int K, H, W;
    private static int[][] map;

    private static class Monkey {
        int r, c, horse;

        public Monkey(int r, int c, int horse) {
            this.r = r;
            this.c = c;
            this.horse = horse;
        }

        @Override
        public String toString() {
            return "Monkey{" +
                    "r=" + r +
                    ", c=" + c +
                    ", horse=" + horse +
                    '}';
        }
    }

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        map = new int[H][W];

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

        //BFS + Output
        System.out.println(bfs());
    }

    private static int bfs() {
        int[] dr = {-1, 0, 1, 0, -2, -1, 1, 2, 2, 1, -1, -2};
        int[] dc = {0, 1, 0, -1, 1, 2, 2, 1, -1, -2, -2, -1};

        int[][] visited = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                visited[i][j] = Integer.MAX_VALUE; // 이거보다 스킬 적게 쓴 원숭이? 여기서도 해봐바
            }
        }

        Queue<Monkey> que = new LinkedList<>();

        que.add(new Monkey(0, 0, 0));
        visited[0][0] = 0;

        int cnt = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                Monkey m = que.poll();
//                System.out.println(m);
                if (m.r == H - 1 && m.c == W - 1) return cnt;

                for (int j = 0; j < 4; j++) {
                    int r = m.r + dr[j];
                    int c = m.c + dc[j];

                    if (0 <= r && r < H && 0 <= c && c < W && visited[r][c] > m.horse && map[r][c] == 0) {
                        que.add(new Monkey(r, c, m.horse));
                        visited[r][c] = m.horse;
                    }
                }

                if (m.horse < K) {
                    for (int j = 4; j < 12; j++) {
                        int r = m.r + dr[j];
                        int c = m.c + dc[j];

                        if (0 <= r && r < H && 0 <= c && c < W && visited[r][c] > m.horse+1 && map[r][c] == 0) {
                            que.add(new Monkey(r, c, m.horse + 1));
                            visited[r][c] = m.horse+1;
                        }
                    }
                }
            }
            cnt++;
        }
        return -1;
    }
}

🔸 코드 해석 🔸

• BFS로 각 움직임 별 경우의 수를 모두 확인한다.
  • 가장 먼저 도착한 경우가 움직임의 최소값이다.
  • 방문 체크를 int 2차원 배열 visited를 이용한다.
    • 말 이동을 최소로 사용할 수록 좋으므로, 더 적은 경우 값을 갱신한다.
  • 원숭이의 이동과 말 이동이 가능한 경우를 모두 큐에 담고 계산을 반복한다.

---

🔸 end 🔸

• 처음엔 말 이동을 K부터 하나씩 차감하는 방식으로 했는데, 코드가 꼬여서 오답이 많아졌다.
  • 다시푸는 과정에서 0부터 K전까지 말 이동을 진행하는 방식으로 바꿨다.