Knight on a Chessboard

문제: Knight on a Chessboard

난이도: Medium

 

문제 설명

 체스의 나이트는 L모양으로 이동한다. Knight(a, b)를 나이트가 한 번에 수직으로 a만큼, 수평으로 b만큼 이동한다는 것으로 정의한다. 정사각형 체스판의 길이 n이 주어졌다면, 나이트가 (0, 0)의 위치에서 (n-1, n-1)까지 가기 위해 최소 몇 번 이동하는지를 구한 값들이 들어있는 2차원 배열을 구하여라.

 구하는 2차원 배열의 크기는 (n-1) x (n-1)이고, [0][0]부터 [n-2][n-2]까지 존재하는 각각의 요소는 a=1, b=1일 때의 결과부터 a=n-1, b=n-1일 때의 결과에 대응한다. 만약 Knight(a, b)가 값을 구할 수 없다면 값을 -1이라고 한다.

 

문제 해결

소스 코드

static int[][] knightlOnAChessboard(int n) {
        int[][] result = new int[n-1][n-1];
        for (int i = 1; i < n; i++) {
            for (int j = i; j < n; j++) {
                result[i - 1][j - 1] = bfs(n, i, j);
            }
        }
        for (int i = 1; i < n - 1; i++) {
            for (int j = 0; j < i; j++) {
                result[i][j] = result[j][i];
            }
        }
        return result;
    }

    private static int bfs(int n, int i, int j) {
        int[] dr = { j, i, j, i, -i, -j, -i, -j };
        int[] dc = { i, j, -i, -j, j, i, -j, -i };

        int curRow = 0;
        int curCol = 0;
        int curDist = 0;

        boolean[][] visited = new boolean[n][n];

        Queue<Coord> queue = new LinkedList<Coord>();
        queue.add(new Coord(0, 0, 0));

        visited[0][0] = true;

        while (!queue.isEmpty()) {
            Coord coord = queue.remove();
            curRow = coord.row;
            curCol = coord.col;
            curDist = coord.dist;

            if (curRow == n - 1 && curCol == n - 1) {
                return curDist;
            }

            for (int k = 0; k < 8; k++) {
                if (curRow + dr[k] >= 0 && curCol + dc[k] >= 0 && curRow + dr[k] < n && curCol + dc[k] < n && !visited[curRow + dr[k]][curCol + dc[k]]) {
                    queue.add(new Coord(curRow + dr[k], curCol + dc[k], curDist + 1));
                    visited[curRow + dr[k]][curCol + dc[k]] = true;
                }
            }
        }
        queue.clear();

        return -1;
    }

    public static class Coord {
        int row, col, dist;
        public Coord(int row, int col, int dist) {
            this.row = row;
            this.col = col;
            this.dist = dist;
        }
    }

 

해설

 최단거리를 구할 때에는 BFS(너비우선탐색)이 이용된다. BFS에는 선입 선출을 하는 자료 구조인 큐가 사용된다.

 큐에서 저장된 정보를 빼내서 다음으로 이동할 수 있는 지점이 있을 때마다 그 지점에 대한 정보(row, col, dist)를 큐에 추가하고, 이미 방문했다는 표시를 한다. 다음으로 이동할 수 있는 지점이 없다면 큐에서 다른 정보를 빼낸다. 큐에 추가될 때마다 거리에 대한 정보 dist를 담을 때 현재 dist+1의 값을 넣어 거리를 구할 수 있다. 도착 지점에 도달하면 그 시점의 dist를 리턴하고, 모든 정보를 빼내서 큐가 빌 때까지 도착 지점에 도달하지 못했다면 -1을 리턴한다.

 이 일련의 과정을 a, b의 값을 변화시켜가며 반복하면 문제의 답을 얻을 수 있다.