[백준 7562] 나이트의 이동 [java]

---

bfs를 이용하여 매우 쉽게 해결한 문제이다.

다른 문제랑 달랐던 부분은 나이트의 이동이기 때문에 움직이는 곳이 상,하,좌,우가 아니라 8곳이나 된다는 것이었다.

하지만 그 부분은 전역 배열을 선언해둬서 쉽게 해결해줬고

요번 문제는 x와 y의 class를 따로 만들지 않고 queue에 x따로 y따로 만들어 줘봤다.

 

코드

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class knight_move {
    static int[] dx = {-2,-1,2,1,-2,-1,1,2};
    static int[] dy = {1,2,1,2,-1,-2,-2,-1};
    static int[][] map;
    static boolean[][] visit;
    static int x,y,gx,gy,limit;
    static int answer = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i<n;i++){
            limit = sc.nextInt();
            map = new int[limit][limit];
            visit = new boolean[limit][limit];
            x = sc.nextInt();
            y = sc.nextInt();
            gx = sc.nextInt();
            gy = sc.nextInt();

            bfs();
            System.out.println(map[gx][gy]);
        }
    }

    private static void bfs() {
        if(x == gx && y == gy){
            return;
        }

        Queue<Integer> queuex = new LinkedList<>();
        Queue<Integer> queuey = new LinkedList<>();

        queuex.add(x);
        queuey.add(y);
        visit[x][y] = true;

        while(!queuex.isEmpty()){
            int a = queuex.poll();
            int b = queuey.poll();

            for(int i = 0; i<dx.length;i++){
                int x1 = a + dx[i];
                int y1 = b + dy[i];

                if(x1>=0 && x1<limit && y1>=0 && y1<limit && !visit[x1][y1]){
                    queuex.add(x1);
                    queuey.add(y1);

                    visit[x1][y1] = true;

                    map[x1][y1] = map[a][b] + 1;
                }
            }
        }
    }
}