[백준] 16952번 체스판 여행2

문제 설명

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

문제 풀이

• 조금 구현이 복잡한 BFS 정도이다.
• bfs를 진행하며 가지치기를 위해 방문체크를 하였는데 체크에 사용된 배열 설명은 아래와 같다.

chk[x좌표][y좌표][말의 종류][현재 도달한 번호] = 말 바꾼 횟수
방문 체크시에 위 배열의 동일 인덱스의 배열값보다 말 바꾼 횟수가 적은 경우에만 큐에 넣어주는 형식으로 진행하였다.
(동일 배열 인덱스일 경우 말 바꾼 횟수가 같거나 높은 경우 해당 노드로 진행 안해도 되기 때문)

소스 코드 (JAVA)

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

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, sx, sy;
    public static int[][] map;
    public static int[][][][] chk;
    //말 이동 관련 -> 0: 나이트, 1: 비숍, 2:룩
    public static int[][] dx = {{-2, -1, 1, 2, 2, 1, -1, -2},{-1, 1, 1, -1},{-1, 0, 1, 0}};
    public static int[][] dy = {{1, 2, 2, 1, -1, -2, -2, -1},{1, 1, -1, -1},{0, 1, 0, -1}};

    public static class Point {
        int x, y, mal, n, cnt, t;
        public Point(int x, int y, int mal, int n, int cnt, int t) {
            this.x = x;
            this.y = y;
            this.mal = mal;
            this.n = n;
            this.cnt = cnt;
            this.t = t;
        }
    }

    public static void solve() throws IOException {
        int resTime = Integer.MAX_VALUE;
        int resCnt = Integer.MAX_VALUE;
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(sx, sy, 0, 1, 0, 0));
        chk[sx][sy][0][1] = 0;
        q.add(new Point(sx, sy, 1, 1, 0, 0));
        chk[sx][sy][1][1] = 0;
        q.add(new Point(sx, sy, 2, 1, 0, 0));
        chk[sx][sy][2][1] = 0;
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.n == (int)Math.pow(N, 2)) {
                if (cur.t < resTime) {
                    resTime = cur.t;
                    resCnt = cur.cnt;
                } else if (cur.t == resTime) {
                    if (cur.cnt < resCnt)
                        resCnt = cur.cnt;
                }
                continue;
            }
            //1. 말 바꾸기
            for (int i = 0; i < 3; i++) {
                if (i == cur.mal) continue;
                if (cur.cnt + 1 >= chk[cur.x][cur.y][i][cur.n]) continue;
                chk[cur.x][cur.y][i][cur.n] = cur.cnt + 1;
                q.add(new Point(cur.x, cur.y, i, cur.n, cur.cnt + 1, cur.t + 1));
            }
            //2. 말 이동
            // 나이트 일 때
            if (cur.mal == 0) {
                for (int d = 0; d < 8; d++) {
                    int X = cur.x + dx[0][d];
                    int Y = cur.y + dy[0][d];
                    if (X < 0 || Y < 0 || X >= N || Y >= N) continue;
                    int N = map[X][Y] == cur.n + 1 ? cur.n + 1 : cur.n;
                    if (cur.cnt >= chk[X][Y][cur.mal][N]) continue;
                    chk[X][Y][cur.mal][N] = cur.cnt;
                    q.add(new Point(X, Y, cur.mal, N, cur.cnt, cur.t + 1));
                }
            }
            // 비숍이나 룩일 때
            else {
                for (int d = 0; d < 4; d++) {
                    int X = cur.x;
                    int Y = cur.y;
                    while(true) {
                        X += dx[cur.mal][d];
                        Y += dy[cur.mal][d];
                        if (X < 0 || Y < 0 || X >= N || Y >= N) break;
                        int N = map[X][Y] == cur.n + 1 ? cur.n + 1 : cur.n;
                        if (cur.cnt >= chk[X][Y][cur.mal][N]) continue;
                        chk[X][Y][cur.mal][N] = cur.cnt;
                        q.add(new Point(X, Y, cur.mal, N, cur.cnt, cur.t + 1));
                    }
                }
            }
        }
        bw.write(resTime + " " + resCnt + "\n");
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        chk = new int[N][N][3][(int)Math.pow(N, 2) + 1];
        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) {
                    sx = i;
                    sy = j;
                }
                for (int k = 0; k < 3; k++)
                    Arrays.fill(chk[i][j][k], Integer.MAX_VALUE);
            }
        }

    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        solve();
        bw.flush();
        bw.close();
        bw.close();
    }
}