백준 7562 나이트의 이동(JAVA) - BFS

백준 7562번

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

문제설명

체스판에서 나이트 (위의 그림처럼 대각선으로 이동가능함)가 몇번만에 이동가능한지 알아내는 문제

체스판의 변의 길이가 주어지고, 초기위치와 도착위치를 입력받는다.

 

 

접근

BFS로 접근 ( 기본이 상하좌우 라면 이 문제는 좌표를 각각 대각선에 맞춰 설정)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int[][] map;
    static boolean[][] visit;
    static Queue<int[]> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            q = new LinkedList<>();
            int I = Integer.parseInt(br.readLine());
            map = new int[I][I];
            visit = new boolean[I][I];
            StringTokenizer tk = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(tk.nextToken());
            int y1 = Integer.parseInt(tk.nextToken());
            tk = new StringTokenizer(br.readLine());
            int x2 = Integer.parseInt(tk.nextToken());
            int y2 = Integer.parseInt(tk.nextToken());

            q.offer(new int[] {x1,y1});
            visit[x1][y1] = true;

            while(!q.isEmpty()){
                int []temp = q.poll();
                int x = temp[0];
                int y = temp[1];

                if(x == x2 && y == y2)
                    break;

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

                    if(nx<0 || ny <0 || nx>=I || ny >=I) continue;
                    if(visit[nx][ny] || map[nx][ny]!=0) continue;
                    map[nx][ny] = map[x][y] + 1;
                    q.offer(new int[] {nx,ny});
                }
            }
            System.out.println(map[x2][y2]);
        }
    }
}