[BOJ] 7562 나이트의 이동

나이트의 이동

풀이

• 최소 몇번 만에 이동할 수 있는지 를 요구했기 때문에 bfs로 풀어야 된다고 생각함.
• 일반 8방탐색이 아니고, 좀 더 퍼진(?) 8방탐색
• Queue에 int[] {x,y,cnt} 배열을 넣어, 직전 cnt+1 하는 방식으로 진행

코드

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

public class BOJ7562 {
    
    static int answer = 0;
    static int[] dx = {-2,-2,-1,1,2,2,1,-1};
    static int[] dy = {-1,1,2,2,1,-1,-2,-2};
    static int I;
    static int[][] map;
    static boolean[][] visited;
    static int curX, curY, moveX, moveY;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            I = Integer.parseInt(br.readLine());
            map = new int[I][I];
            visited = new boolean[I][I];
            answer = 0;
            st = new StringTokenizer(br.readLine());
            curX = Integer.parseInt(st.nextToken());
            curY = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            moveX = Integer.parseInt(st.nextToken());
            moveY = Integer.parseInt(st.nextToken());

            bfs(curX, curY);
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }

    private static void bfs(int x, int y) {
        visited[x][y] = true;
        Queue<int[]> queue = new LinkedList<>();
        int cnt = 0;
        queue.offer(new int[] { x, y,cnt });
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int xx = cur[0];
            int yy = cur[1];
            int cCnt = cur[2];
            if (xx == moveX && yy == moveY) {
                answer = cCnt;
                break;
            }
            else {
                for (int i = 0; i < 8; i++) {
                    int nx = xx + dx[i];
                    int ny = yy + dy[i];
                    if (nx >= 0 && nx < I && ny >= 0 && ny < I && !visited[nx][ny]) {
                        queue.offer(new int[] { nx, ny, cCnt + 1 });
                        visited[nx][ny] = true;
                    }
                }
            }

        }

    }
}