[JAVA/16948번] 데스 나이트

---

문제

---

입력 및 출력

---

풀이

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

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

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

        // 체스판의 크기 N
        N = Integer.parseInt(br.readLine());

        // 해당 위치에 방문했음을 표시하는 변수
        visited = new boolean[N + 1][N + 1];

        // 출발지점과 도착지점을 각 변수에 할당
        String[] temp = br.readLine().split(" ");
        int r1 = Integer.parseInt(temp[0]);
        int c1 = Integer.parseInt(temp[1]);
        int r2 = Integer.parseInt(temp[2]);
        int c2 = Integer.parseInt(temp[3]);

        // bfs 함수 호출
        bfs(r1, c1, r2, c2);
    }

    public static void bfs(int r1, int c1, int r2, int c2) {
        // Node타입을 갖는 큐 선언
        Queue < Node > queue = new LinkedList < > ();

        // queue에 시작 위치를 넣고, 방문처리를 한다.
        queue.add(new Node(r1, c1, 0));
        visited[r1][c1] = true;

        while (!queue.isEmpty()) {
            Node curPos = queue.poll();

            // 도착지점과 일치할 경우, 횟수를 화면에 출력하고 return
            if (curPos.x == r2 && curPos.y == c2) {
                System.out.println(curPos.count);
                return;
            }

            // 이동할 수 있는 방법은 총 6개이기 때문에 6만큼 반복수행
            for (int i = 0; i < 6; i++) {
                // 현재의 위치에서 i번째 요소에 값을 더해준다.
                int nx = curPos.x + dx[i];
                int ny = curPos.y + dy[i];

                // 범위안에 들고 방문하지 않은 곳일경우
                if (isRange(nx, ny) && !visited[nx][ny]) {
                    queue.add(new Node(nx, ny, curPos.count + 1));
                    visited[nx][ny] = true;
                }
            }

        }
        // 그외의 경우는 갈 수 없는 방법이기 때문에 -1을 출력
        System.out.println(-1);
    }

    public static boolean isRange(int x, int y) {
        if (x >= 0 && y >= 0 && x <= N && y <= N) {
            return true;
        }
        return false;
    }
}

class Node {
    // x축, y축, 이동횟수
    int x, y, count;

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

---

결과 및 해결방법

[결과]

[정리]

해결방법
알고리즘 배너를 확인하면 해당 문제는 너비우선탐색 문제인 것을 확인할 수 있다.

데스 나이트가 이동할 수 있는 방법은 총 6가지로 문제에 표기되어 있다. 이 부분을 "어떻게 표시하면 좋을까?" 고민하다, x축만 갖는 배열과 y축만 갖는 배열을 따로 만들어 값을 할당하였다.

문제의 요구사항에서 NxN의 크기를 갖는 체스판이 존재하기 때문에 visited배열 또한 2차원 배열로 선언하고 N+1만큼의 크기를 할당하였다.

노드 클래스는 x, y, count의 값을 갖고있고 각 항목은 x축의 값, y축의 값, 이동횟수의 의미를 갖는다. 생성자를 통해 매개변수로 받아온 값을 변수에 대입한다.

너비우선탐색을 수행하기 위해 큐를 선언하였다. 큐에 시작위치인 r1, c1 그리고 이동횟수인 0을 넣는다. 또한 해당 위치는 방문하였기 때문에 visited배열의 r1과 c1의 인덱스에 true값을 넣어준다.

다음으로 큐가 비어있지 않을 경우까지 반복문을 수행한다. 큐에 가장 앞에 있는 원소를 꺼내어 변수에 저장하고, 해당 위치의 x축과 y축이 목표지점인 r2, c2의 값과 동일한지 판단을 한다. 만약 동일할 경우 이동횟수를 화면에 출력하고 return한다.

이동할 수 있는 방법은 총 6개이기 때문에 6만큼 반복문을 수행한다. 이동 후 x위치와 y위치의 값을 받아 저장하고 해당 위치가 방문하지 않은 경우 위와 동일한 방식으로 계속해서 처리한다.

그 외의 경우는 갈 수 없는 경로이기 때문에 -1을 화면에 출력한다.