[알고리즘 PS] 백준 7562 나이트의 이동 자바 문제풀이

문제

해당 포스팅은 백준의 7562 나이트의 이동 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

7562번: 나이트의 이동

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이 문제는 BFS 를 이용해서 나이트가 이동할 수 있는 경로를 큐에 넣고 탐색을 하면 되는 문제이다.

 

정답 코드

public class Main {

    private static int[] posX = {-1, -2, -2, -1, 1, 2, 2, 1};
    private static int[] posY = {-2, -1, 1, 2, 2, 1, -1, -2};

    private static int[][] arr;

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

        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            int l = Integer.parseInt(br.readLine());

            arr = new int[l][l];

            String[] from = br.readLine().split(" ");
            String[] to = br.readLine().split(" ");

            int fromX = Integer.parseInt(from[0]);
            int fromY = Integer.parseInt(from[1]);

            int toX = Integer.parseInt(to[0]);
            int toY = Integer.parseInt(to[1]);

            arr[fromY][fromX] = 1;

            int result = bfs(fromX, fromY, toX, toY, l) - 1;

            bw.write(result + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static int bfs(int fromX, int fromY, int toX, int toY, int l) {
        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(fromX, fromY));

        while(!queue.isEmpty()) {
            Position front = queue.remove();

            if(front.x == toX && front.y == toY) {
                return arr[front.y][front.x];
            }

            for (int i = 0; i < 8; i++) {
                int xx = front.x + posX[i];
                int yy = front.y + posY[i];

                if(0 <= xx && xx < l && 0 <= yy && yy < l) {
                    if(arr[yy][xx] == 0) {
                        queue.add(new Position(xx, yy));
                        arr[yy][xx] = arr[front.y][front.x] + 1;
                    }
                }
            }
        }

        return -1;
    }

    private static class Position {
        int x;
        int y;

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

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.