백준 1600번 : 말이 되고픈 원숭이 자바

🧫 문제 분석

 

✔️ 출처

말이 되고픈 원숭이 골드 3

 

📖 문제

 

상하좌우, 체스의 나이트 이동방식을 BFS 방식으로 푸는 문제이다.

 

이 문제에서 핵심은 

말 움직임은 k번만 가능하다

이때 중요한 것은 0~k번 말 움직임의 경우를 각각 따져서 가장 빠르게 오른쪽 끝으로 도달한 경우를 찾는 것이다.

 

말 움직임을 0번도 안쓰고 상하좌우로만 목표점에 도달한 경우

말 움직임을 1번 쓰고 상하좌우로만 목표점에 도달한 경우

...

말 움직임을 k번 쓰고 상하좌우로만 목표점에 도달한 경우

 

이때 각 말 움직임 횟수마다 방문 체크를 해줘야한다.

 

 

말 움직임 구현

상하좌우로 먼저 탐색을 하고

그 방향으로 1번 더 간 다음

상하일 경우 좌우를 탐색

좌우일 경우 상하를 탐색한다.

 

코드와 그림을 보면 이해하기 쉽다.

 

 

 

 

이와 비슷한 문제를 남길테니 먼저 풀어보는 것도 좋다.

백준 2206번 벽 부수고 이동하기 골드 3

 

 

 

---

🔅 문제 풀이

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

public class Main {
    static int[][] graph;
    static boolean[][][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int k = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());

        graph = new int[h][w];
        visited = new boolean[h][w][31];

        // 그래프 값 초기화 (평지 생성중...)
        for (int i = 0; i < h; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < w; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bw.write( bfs(h - 1, w - 1, k) + "\n");

        bw.flush();
        bw.close();
    }

    private static int bfs(int h, int w, int cnt) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, cnt, 0}); // {y, x , k, 이동횟수}
        visited[0][0][cnt] = true;

        int min = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            int[] loc = q.poll();

            if (loc[0] == h && loc[1] == w) {
                return loc[3];
            }

            for (int i = 0; i < 4; i++) {
                int nextY = loc[0] + dy[i];
                int nextX = loc[1] + dx[i];
                int k = loc[2];


                // 말 처럼 이동
                if (k > 0) {
                    // 좌우 탐색 및 이동
                    if (i < 2) {
                        for (int j = 2; j < 4; j++) {
                            int horseY = nextY + dy[i] + dy[j];
                            int horseX = nextX + dx[i] + dx[j];

                            if (!checkBound(horseY, horseX, k - 1)) {
                                q.add(new int[]{horseY, horseX, k - 1, loc[3] + 1});
                                visited[horseY][horseX][k - 1] = true;
                            }
                        }

                        // 상하 탐색 및 이동
                    } else {
                        for (int j = 0; j < 2; j++) {
                            int horseY = nextY + dy[i] + dy[j];
                            int horseX = nextX + dx[i] + dx[j];

                            if (!checkBound(horseY, horseX, k - 1)) {
                                q.add(new int[]{horseY, horseX, k - 1, loc[3] + 1});
                                visited[horseY][horseX][k - 1] = true;
                            }
                        }
                    }
                }

                if (!checkBound(nextY, nextX, k)) {
                    q.add(new int[]{nextY, nextX, k, loc[3] + 1});
                    visited[nextY][nextX][k] = true;
                }
            }
        }
        return -1;
    }
    
	// 배열 범위 및 장애물 체크
    private static boolean checkBound(int nextY, int nextX, int k) {
        return nextY < 0 || nextY >= graph.length ||
                nextX < 0 || nextX >= graph[0].length || visited[nextY][nextX][k] || 
                graph[nextY][nextX] == 1;
    }

}

 

 

리팩토링

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

public class Main {
    static int[][] graph;
    static boolean[][][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int k = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());

        graph = new int[h][w];
        visited = new boolean[h][w][31];

        // 그래프 값 초기화 (평지 생성중...)
        for (int i = 0; i < h; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < w; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bw.write( bfs(h - 1, w - 1, k) + "\n");
        bw.flush();
        bw.close();
    }

    private static int bfs(int h, int w, int cnt) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, cnt, 0});
        visited[0][0][cnt] = true;

        int min = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            int[] loc = q.poll();

            if (loc[0] == h && loc[1] == w) {
                return loc[3];
            }

            for (int i = 0; i < 4; i++) {
                int nextY = loc[0] + dy[i];
                int nextX = loc[1] + dx[i];
                int k = loc[2];

                // 말 처럼 이동
                if (k > 0) {
                    int idx = i < 2 ? 2 : 0;

                    for (int j = idx; j < idx + 2; j++) {
                        int horseY = nextY + dy[i] + dy[j];
                        int horseX = nextX + dx[i] + dx[j];

                        if (!checkBound(horseY, horseX, k - 1)) {
                            q.add(new int[]{horseY, horseX, k - 1, loc[3] + 1});
                            visited[horseY][horseX][k - 1] = true;
                        }
                    }
                }

                if (!checkBound(nextY, nextX, k)) {
                    q.add(new int[]{nextY, nextX, k, loc[3] + 1});
                    visited[nextY][nextX][k] = true;
                }
            }
        }
        return -1;
    }

    private static boolean checkBound(int nextY, int nextX, int k) {
        return nextY < 0 || nextY >= graph.length ||
                nextX < 0 || nextX >= graph[0].length || 
                visited[nextY][nextX][k] || graph[nextY][nextX] == 1;
    }

}

 

사실 푸는데 엄청 오래걸렸다. 

정말 많이 틀렸고... 하지만 이러한 유형의 문제에 대해서 배우게 되었으니 좋은 경험이라고 생각한다. 

 

 

❗ 오답노트 / 필요한 지식

1.  그래프 탐색 문제에서 목표지점까지 갈 수 있는 수단 혹은 방법이 여러 개인 경우 3중 배열을 사용하여 각 경우에 대해서 방문을 체크해줘야한다!!!!!!