백준 7565 : 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력 1 복사

5
28
0

 

• 풀이

 

미로 탐색과 거의 비슷하고, 여긴 갈수 있는칸 없는칸이 없어서 풀긴 더 수월했다

인풋 받는데서 한자리만 오는줄 알고 s.charAt(0), s.charAt(0)으로 했다가 "30 50" 받을때 공백이 들어가서

StringTokenizer로 수정했다.. 인풋 받는 방법도 좀 더 찾아봐야겠다

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

public class Main{

    static int T, N, startX, startY, targetX, targetY;;

    static String s;
    static StringTokenizer st;

    static int[][] board;
    static boolean[][] visit;
    static int[][] dist;

    static int[][] dir = {{2,1}, {1,2}, {-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

    static void bfs(int x, int y){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        queue.add(y);
        visit[x][y] = true;
        dist[x][y] = 0;

        while (!queue.isEmpty()){
            x = queue.poll();
            y = queue.poll();
            // 나이트는 8방향 dir로 이동 가능하다
            for (int i = 0; i < 8; i++){
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];
                if (dx < 0 || dy < 0 || dx >= N || dy >= N) continue;
                if (visit[dx][dy]) continue;
                queue.add(dx);
                queue.add(dy);
                visit[dx][dy]= true;
                dist[dx][dy] = dist[x][y] +1;
            }
        }
    }


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

        while (T-- > 0){
            N = Integer.parseInt(br.readLine());
            board = new int[N][N];
            visit = new boolean[N][N];
            dist = new int[N][N];
            s = br.readLine();
            st = new StringTokenizer(s);
            startX = Integer.parseInt(st.nextToken());
            startY = Integer.parseInt(st.nextToken());
            s = br.readLine();
            st = new StringTokenizer(s);
            targetX = Integer.parseInt(st.nextToken());
            targetY = Integer.parseInt(st.nextToken());
            bfs(startX,startY);
            System.out.println(dist[targetX][targetY]);
        }
    }
}