[ 백준 16959 ] 체스판 여행 1

1. 문제

16959번: 체스판 여행 1

 

2. 풀이

BFS를 응용해볼 수 있는 좋은 유형의 문제로, 문제의 조건에 따라 말의 방문 처리를 어떻게 꼼꼼하게 할 것 인가가 문제의 키 포인트이다. 먼저 지학이가 수행할 수 있는 동작과 조건을 살펴보자.

 

1) 동작

• 말을 다른 유형의 말로 변경한다(나이트, 룩, 비숍)
• 말을 이동시킨다

2) 조건

• 같은 칸을 여러 번 방문해도 된다.
• 1부터 N² 까지 각 칸을 순차적으로 방문해야 한다.

 

---

번호에 따라 순차적으로 방문해야 하므로, 체스판을 입력 받음과 동시에 1번(시작 지점) 칸이 어디에 있는지 미리 파악해둔다.

다음으로 방문처리를 위해서는 4차원 배열이 필요한데 형태를 살펴보자.

// 행, 열, 출발노드, 말의 유형
boolean[][][][] visit = new boolean[N][N][N * N + 1][3]

출발노드의 경우, 현재 K번에서 출발해 K + 1번을 탐색하고 있는 과정인지를 확인하는 용도이며, 말의 유형의 경우 3가지 유형의 말이 각 상황에 맞게 방문했는가 여부를 확인하는 것이다.

이 방문배열을 이용해 말의 방문 처리만 잘 수행해준다면, 각 말의 유형에 따라 적절히 이동시키거나 말을 변경시켜주는 작업만 BFS로 수행하면 된다.

 

3. 소스코드

public class Main {

    static int N;
    static int[][] map;
    static boolean[][][][] visit;

    static int solve(int startY, int startX) {
        int ret = Integer.MAX_VALUE;

        Queue<ChessPiece> q = new LinkedList<>();

        for (int type = 0; type < 3; type++) {
            q.add(new ChessPiece(startY * N  + startX, type, 0, 1));
            visit[startY][startX][1][type] = true;
        }

        while (!q.isEmpty()) {
            ChessPiece now = q.poll();
            int y = now.pos / N;
            int x = now.pos % N;

            if (now.current == N * N) {
                ret = Math.min(ret, now.count);
                continue;
            }

            // 말 교체
            for (ChessPieceType type : ChessPieceType.values()) {
                if (now.getType() == type || visit[y][x][now.current][type.getIdx()]) continue;
                visit[y][x][now.current][type.getIdx()] = true;
                q.add(new ChessPiece(now.pos, type.getIdx(), now.count + 1, now.current));
            }

            ChessPieceType type = now.getType();
            if (type == ChessPieceType.KNIGHT) {
                for (int dir = 0; dir < 8; dir++) {
                    int ny = y + type.getDy()[dir];
                    int nx = x + type.getDx()[dir];

                    ChessPiece next = canContinueThenGetNextNode(ny, nx, now.current, type.getIdx(), now.count);
                    if (next != null) {
                        q.add(next);
                    }
                }
            } else if (now.getType() == ChessPieceType.ROOK) {
                for (int dir = 0; dir < 4; dir++) {
                    for (int offset = 1; offset < N; offset++) {
                        int ny = y + type.getDy()[dir] * offset;
                        int nx = x + type.getDx()[dir] * offset;

                        ChessPiece next = canContinueThenGetNextNode(ny, nx, now.current, type.getIdx(), now.count);
                        if (next != null) {
                            q.add(next);
                        }
                    }
                }
            } else {
                for (int dir = 0; dir < 4; dir++) {
                    for (int offset = 1; offset < N; offset++) {
                        int ny = y + type.getDy()[dir] * offset;
                        int nx = x + type.getDx()[dir] * offset;

                        ChessPiece next = canContinueThenGetNextNode(ny, nx, now.current, type.getIdx(), now.count);
                        if (next != null) {
                            q.add(next);
                        }
                    }
                }
            }

        }

        return ret;
    }

    static ChessPiece canContinueThenGetNextNode(int ny, int nx, int current, int typeIdx, int count) {
        if (isOutOfRange(ny, nx)) return null;
        if (map[ny][nx] == current + 1) {
            current++;
        }
        if (visit[ny][nx][current][typeIdx]) return null;

        visit[ny][nx][current][typeIdx] = true;
        return new ChessPiece(ny * N + nx, typeIdx, count + 1, current);
    }

    static boolean isOutOfRange(int y, int x) {
        return y < 0 || x < 0 || N <= y || N <= x;
    }

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

        map = new int[N][N];
        visit = new boolean[N][N][N * N + 1][3];

        int y = 0, x = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    y = i;
                    x = j;
                }
            }
        }

        int ans = solve(y, x);

        bw.write(ans + "");
        bw.flush();
        bw.close();
        br.close();
    }

    // 정점의 역할을 해줄 클래스(위치, 말 유형, 움직임 수, 출발 좌표 번호)
    static class ChessPiece {
        int pos, type, count, current;

        public ChessPiece(int pos, int type, int count, int current) {
            this.pos = pos;
            this.type = type;
            this.count = count;
            this.current = current;
        }

        ChessPieceType getType() {
            return ChessPieceType.getType(this.type);
        }
    }

    // 체스 말 유형에 따른 움직임 정의
    enum ChessPieceType {
        KNIGHT(0, new int[]{-1, -2, -2, -1, 1, 2, 2, 1}, new int[]{-2, -1, 1, 2, 2, 1, -1, -2}),
        ROOK(1, new int[]{-1, 0, 1, 0}, new int[]{0, 1, 0, -1}),
        BISHOP(2, new int[]{-1, -1, 1, 1}, new int[]{-1, 1, -1, 1});

        final int idx;
        final int[] dy;
        final int[] dx;

        ChessPieceType(int idx, int[] dy, int[] dx) {
            this.idx = idx;
            this.dy = dy;
            this.dx = dx;
        }

        public int[] getDy() {
            return dy;
        }

        public int[] getDx() {
            return dx;
        }

        public int getIdx() {
            return idx;
        }

        static ChessPieceType getType(int idx) {
            if (idx == 0) return KNIGHT;
            if (idx == 1) return ROOK;
            return BISHOP;
        }
    }
}​

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code

---

BFS 개념은 아래 게시글 참고♥️

그래프와 BFS(Graph & Breadth First Search)