[BFS/자바] 코드트리 IL. 나이트

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제 또한 최단 경로를 묻는 문제이므로 BFS로 접근하면 된다.

 

풀이

자바는 0으로 배열이 기본 초기화되니, 처음에는 0이면 이동이 불가한 것이라고 생각했다.

public class 나이트 {
    private static int n;
    private static int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
    private static int[] dy = new int[]{-1, -2, -2, -1, 1, 2, 2, 1};
    private static int x1, y1, x2, y2;
    private static int[][] ans;
    private static Queue<Pair> q = new LinkedList<>();
    private static int[][] visited;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        visited = new int[n][n];
        ans = new int[n][n];

        st = new StringTokenizer(br.readLine());
        x1 = Integer.parseInt(st.nextToken())-1;
        y1 = Integer.parseInt(st.nextToken())-1;
        x2 = Integer.parseInt(st.nextToken())-1;
        y2 = Integer.parseInt(st.nextToken())-1;

        BFS();
        if (ans[y2][x2] > 0) {
            System.out.println(ans[y2][x2]);
        } else {
            System.out.println(-1);
        }

    }

    private static void BFS() {
        q.add(new Pair(x1, y1));
        visited[y1][x1] = 1;

        while (!q.isEmpty()) {
            Pair p = q.poll();
            int curX = p.getX();
            int curY = p.getY();

            for (int i = 0; i < 8; i++) {
                int newY = curY + dy[i];
                int newX = curX + dx[i];
                if (inRange(newX, newY) && visited[newY][newX] == 0) {
                    q.add(new Pair(newX, newY));
                    visited[newY][newX] = 1;
                    ans[newY][newX] = ans[curY][curX] + 1;
                }
            }
        }
    }

    private static class Pair {
        private int x;
        private int y;

        public int getX() {
            return this.x;
        }
        public int getY() {
            return this.y;
        }

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

    private static boolean inRange(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }

}

하지만 1 1 에서 1 1로 이동하는 경우를 가정한다면 출력이 0이 되어야 한다.

 

따라서 -1로 배열을 초기화하고, 시작점을 0으로 입력한 뒤에 BFS를 돌리고 목표지점을 출력하면 정답인 로직이 된다.

public class Main {
    private static int n;
    private static int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
    private static int[] dy = new int[]{-1, -2, -2, -1, 1, 2, 2, 1};
    private static int x1, y1, x2, y2;
    private static int[][] arr;
    private static Queue<Pair> q = new LinkedList<>();
    private static int[][] visited;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        visited = new int[n][n];
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = -1;
            }
        }

        st = new StringTokenizer(br.readLine());
        x1 = Integer.parseInt(st.nextToken())-1;
        y1 = Integer.parseInt(st.nextToken())-1;
        x2 = Integer.parseInt(st.nextToken())-1;
        y2 = Integer.parseInt(st.nextToken())-1;

        BFS();
        System.out.println(arr[y2][x2]);

    }

    private static void BFS() {
        q.add(new Pair(x1, y1));
        arr[y1][x1] = 0;
        visited[y1][x1] = 1;

        while (!q.isEmpty()) {
            Pair p = q.poll();
            int curX = p.getX();
            int curY = p.getY();

            for (int i = 0; i < 8; i++) {
                int newY = curY + dy[i];
                int newX = curX + dx[i];
                if (inRange(newX, newY) && visited[newY][newX] == 0) {
                    q.add(new Pair(newX, newY));
                    visited[newY][newX] = 1;
                    arr[newY][newX] = arr[curY][curX] + 1;
                }
            }
        }
    }

    private static class Pair {
        private int x;
        private int y;

        public int getX() {
            return this.x;
        }
        public int getY() {
            return this.y;
        }

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

    private static boolean inRange(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }

}