[BOJ 7562] 나이트의 이동 (JAVA)

[문제링크]

7562번: 나이트의 이동

[배운점]

- 문제에서 '최소 몇 번만에 이동할 수 있는지' => BFS를 떠올리자..!

- 단순히 재귀로 또 풀어내야겠네~했다가 stack over flow에 걸렸다. (이동 횟수를 직접 매개변수로 전달해주면서 카운트했었음)

- 이런 문제를 접하면 이동 횟수를 배열에 저장해나가는 방식으로 하면 편리한 것 같다.

- 맞추고 다른 사람들의 코드를 보다보니 입출력에 BufferedReader, 문자열 다룰때 StringTockenizer를 많이 사용한다.
(나는 아직 이게 익숙해지지가 않아서 Scanner로...사용하는데 익숙해지는게 좋겠지..!?)

 

[기본 로직 OR IDEA]

- 해당 위치에서 이동이 가능한 지점 8곳을 구한다.

- 최소 거리를 구해야하니까 이전 거리에서 다음으로 이동할 때 방문한적이 있는지를 체크한다
(나는 chess[nx][ny]가 0이면 방문하지 않았다고 생각했다.)

- 찾는 위치(rx, ry)와 현재 위치가 일치하면 체스의 목적지를 출력한다.

 

[코드]

import java.util.*;

public class Main {
    static int[] dx = {1, 2, 1, 2, -1, -2, -1, -2};
    static int[] dy = {2, 1, -2, -1, 2, 1, -2, -1};
    static int[][] chess;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int tc = sc.nextInt();

        for (int t = 0; t < tc; t++) {
            int n = sc.nextInt();
            chess = new int[n][n];
            int cx = sc.nextInt();
            int cy = sc.nextInt();
            int rx = sc.nextInt();
            int ry = sc.nextInt();

            search(cx, cy, rx, ry, n);
            System.out.println(chess[rx][ry]);
        }

    }

    private static int search(int cx, int cy, int rx, int ry, int n) {
        Queue<XY> q = new LinkedList<>();
        q.add(new XY(cx, cy));

        while(!q.isEmpty()){
            var xy = q.poll();

            if (xy.x == rx && xy.y == ry) {
                return chess[rx][ry] - 1;
            }

            for (int i = 0; i < 8; i++) {
                int nx = xy.x + dx[i];
                int ny = xy.y + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= n || chess[nx][ny] != 0) continue;

                chess[nx][ny] = chess[xy.x][xy.y] + 1;
                q.add(new XY(nx, ny));
            }

        }
        return 0;
    }

}

class XY{
    int x;
    int y;

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