[Boj_16509] 장군

📎 문제 링크

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

 

▸ 문제

오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 상을 어떻게 써야 할지 도와주자.

 

 

위 그림은 10×9 크기의 장기판을 나타내며, 상은 (5, 4)에, 왕은 (1, 4)에 자리 잡고 있는 기물이다. (0, 3)과 (2, 5)를 꼭짓점으로 하는 사각형과, (7, 3)과 (9, 5)를 꼭짓점으로 하는 사각형은 왕이 위치할 수 있는 궁성이라고 한다. 상은 위 그림과 같이 8가지 방법으로 움직일 수 있는데, 상, 하, 좌, 우로 한 칸을 이동한 후에 같은 방향 쪽 대각선으로 두 칸 이동한다.

 

 

만약 상이 이동하는 경로에 위 그림과 같이 다른 기물이 있다면 상은 그쪽으로 이동할 수 없다. 또한, 상이 장기판을 벗어날 수도 없다.

10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수를 구하여라.

 

▸ 입력

첫 번째 줄에는 상의 위치를 의미하는 정수 R1, C1이 주어진다.

두 번째 줄에는 왕의 위치를 의미하는 정수 R2, C2가 주어진다. 장기판에서 Ri (0 ≤ Ri ≤ 9)는 행을, Ci (0 ≤ Ci ≤ 8)는 열을 의미한다.

왕은 항상 궁성에 자리 잡고 있으며, 상과 왕의 위치는 겹치지 않는다.

 

▸ 출력

상이 왕에게 도달할 수 있는 최소 이동 횟수를 출력한다. 만약 도달할 수 없다면 -1을 출력한다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 5
• 🔔  문제 유형 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

위 문제는 입력으로 주어진 상 위치에서 너비 우선 탐색(BFS)을 진행하여 왕에게 도달할 수 있는 최소 횟수를 구할 수 있다.

 

주어진 규칙에 따라 상의 이동 경로를 탐색한다.

 

먼저 상하좌우 방향으로 한 칸 이동하는데, 이때 이동하려는 위치가 범위 내에 있으며, 그 위치에  다른 기물이 없을 경우에만 이동이 가능하다.

 

이동 후, 해당 위치에서 두 개의 대각선 방향을 검사한다. 각 상하좌우 방향에 대해 두 개의 대각선 방향을 매칭하여, 첫 번째 대각선 이동이 가능할 경우, 그 위치에서 두 번째 대각선 이동을 진행한다.

마찬가지로 이때 이동하려는 위치가 범위 내에 있으며, 그 위치에  다른 기물이 없을 경우에만 이동이 가능하다.

 

규칙에 따라 이동을 마친 후, 최종적으로 도달한 위치가 범위 내에 있고 방문한 적 없는 경우에만 큐에 추가하여 탐색을 계속한다.

 

큐에서 꺼낸 현재 위치가 왕의 위치와 같다면, 해당 이동 횟수를 반환한다.

만약 모든 탐색을 마쳤는데도 왕에 도달할 수 없다면 -1을 반환한다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 11592KB
시간 : 64ms

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 {
    static final int n = 10, m = 9; // 장기판 크기
    static int r, c;
    static int r2, c2;
    static boolean[][] checked;
    static public class Pos {
        int x; int y; int cnt;
        public Pos(int x, int y, int cnt) {
            this.x = x; this.y = y; this.cnt = cnt;
        }
    }
    // 우하좌상
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    // 대각선
    static int[] zx = {-1, 1, 1, -1};
    static int[] zy = {1, 1, -1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 상의 위치
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        // 왕의 위치
        r2 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());

        checked = new boolean[n][m];

        int ans = bfs(r, c);

        System.out.println(ans);
    }

    private static int bfs(int r, int c) {
        Queue<Pos> que = new LinkedList<>();
        checked[r][c] = true;
        que.offer(new Pos(r, c, 0));

        while (!que.isEmpty()) {
            Pos now = que.poll();

            if (now.x == r2 && now.y == c2) { // 왕 마주치면 이동횟수 반환
                return now.cnt;
            }

            for (int d = 0; d < 4; d++) {
                // 먼저 상하좌우에 따라 한 칸 이동
                int nx = dx[d] + now.x;
                int ny = dy[d] + now.y;

                if (isPossible(nx, ny)) {
                    for (int cnt = 0; cnt < 2; cnt++) { // 두 개의 대각선 방향 탐색
                        // 이동 방향
                        int z = (d+cnt) % 4;
                        // 대각선으로 한 칸 이동
                        int nzx = nx + zx[z];
                        int nzy = ny + zy[z];

                        if (isPossible(nzx, nzy)) {
                            // 기물이 없다면 나머지 한 칸 이동
                            nzx += zx[z];
                            nzy += zy[z];
                            
                            if (rangeCheck(nzx, nzy) && !checked[nzx][nzy]) {
                                que.offer(new Pos(nzx, nzy, now.cnt+1));
                                checked[nzx][nzy] = true;
                            }
                        }
                    }
                }
            }
        }

        return -1;
    }

    // 이동 가능한지 확인
    private static boolean isPossible(int x, int y) {
        if (x == r2 && y == c2) return false; // 상이 이동하는 경로에 왕이 있으면 그 방향으로 이동 불가
        return rangeCheck(x, y); // 범위 내에 있는지 확인
    }

    private static boolean rangeCheck(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
}

 

상하좌우 이동에 따라 대각선 방향 이동을 어떻게 처리해 줘야 할지 꽤 고민했다.

dx, dy 배열과 zx, zy 배열을 각 상하좌우 방향에 대해 두 개의 대각선 방향과 매칭할 수 있도록 설정했다.

이후, z = (d + cnt) % 4 방식으로 각 상하좌우 방향에 대해  두 개의 대각선 방향을 순차적으로 탐색하도록 구현했다. 

이 방식으로 각 상하좌우 방향에 대해 두 개의 대각선 방향을 차례로 탐색하는 로직을 간편하게 구성할 수 있었다.

 

오랜만에 BFS 문제를 풀어서 그런지 재밌게 풀면서 재밌었다. 그런 김에 포스팅까지 완료 ! 😎 🔥

밀린 나머지 포스팅도 얼른 해야지..😂