Red Knight’s Shortest Path

문제: Red Knight’s Shortest Path

난이도: Medium

 

문제 설명

 Red Knight는 다음과 같은 방식으로 체스판을 이동한다고 한다.

 체스판의 크기n, 시작 지점의 row와 col(i_start, j_start), 도착 지점의 row와 col(i_end, j_end)이 주어질 경우, 최단 거리와 이동 경로의 움직임을 출력하여라. 만약 도착 지점에 도달할 수 없다면 Impossible을 출력하여라.

 예를 들어, 7, 0, 3, 4, 3이 주어질 경우 출력 결과는 다음과 같다.

2

LR LL

 

문제 해결

소스 코드

static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) {

        int[] dr = {-2, -2, 0, 2, 2, 0};
        int[] dc = {-1, 1, 2, 1, -1, -2};
        String[] pathArr = {"UL", "UR", "R", "LR", "LL", "L"};

        int curRow = i_start;
        int curCol = j_start;
        int curDist = 0;
        String curPath = "";
        String path = "";

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

        Queue<Coord> queue = new LinkedList<Coord>();
        queue.add(new Coord(curRow, curCol, 0, "", ""));
        visited[0][0] = true;

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

            if (curRow == i_end && curCol == j_end) {
                String[] splitted = curPath.split("->");
                String finalPath = "";
                for(int i = 1; i < splitted.length; i++) {
                    finalPath += (splitted[i]+" ");
                }
                System.out.println(curDist);
                System.out.println(finalPath);
                return;
            }

            for (int k = 0; k < 6; 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, path, pathArr[k]));
                    visited[curRow + dr[k]][curCol + dc[k]] = true;
                }
            }
        }
        queue.clear();

        System.out.println("Impossible");
    }

    public static class Coord {
        int row, col, dist;
        String path;
        public Coord(int row, int col, int dist, String oldPath, String path) {
            this.row = row;
            this.col = col;
            this.dist = dist;
            if(oldPath.equals("")) {
                this.path = "Start";
            } else {
                this.path = oldPath+"->"+path;
            }
        }
    }

 

 

해설

 최단거리를 구할 때에는 BFS(너비우선탐색)이 이용된다. 지난주에 푼 문제인 Knight on a Chessboard와 풀이 과정이 유사하니 해당 문제의 글을 참고하길 바란다.