[백준] 7562번 : 나이트의 이동

7562번: 나이트의 이동

# 문제

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

# 입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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

# 알고리즘 분류

• BFS
• 그래프 이론
• 그래프 탐색

---

이전에 풀었던 '벽 부수고 이동하기' 같은 문제에 비해 훨씬 난이도가 낮아진 문제라고 생각된다. 이 문제에서 주의할 점 2 가지만 들어보자면.

 

• Test Case가 1개 이상이므로 BFS 함수가 끝나면 항상 큐를 비워주어야 한다. (큐를 전역변수로 놓았을 경우)
• 나이트의 이동 방향은 총 8방향이고, 각 도착 지점에 대해 항상 범위를 검사해야 한다.(0 이상, L 미만, L=체스판 한 변의 길이)

실제로 큐를 매번 비워주지 않아서 단일 케이스에 대해서 결과가 제대로 나오는 반면 다중 테스트 케이스를 돌리면 값이 제대로 나오지 않거나 ArrayIndexOutofBoundsException 같은 에러를 뿜어낸다. BFS함수가 끝나면 항상 큐를 비워주자.

 

나이트가 도착할 수 있는 정점은 현재 나이트가 (Y, X) 위치에 있을 때

• (Y-1, X-2)
• (Y-2, X-1)
• (Y-2, X+1)
• (Y-1, X+2)
• (Y+1, X+2)
• (Y+2, X+1)
• (Y+2, X-1)
• (Y+1, X-2)

의 위치로 갈 수 있다. 

int graph[][];

BFS(startY, startY, endY, endX)
{
	graph[startY][startX] -> 1
    enqueue(startY, startX)
    
    while(!Q.isEmpty):
    	y -> dequeue(y)
        x -> dequeue(x)
        
        if(y == endY && x == endX) then
        	print(graph[y][x])
            Q.clear()
            break;
        
        if(도착할 수 있는 정점 8개에 대해 범위 검사) then
        	if(방문한 적이 없다면) then
            	graph[다음 Y][다음 X] -> graph[y][x] + 1
                enqueue(다음 Y, 다음 X)
}

# Whole Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int y, int x){ this.y=y; this.x=x;}
    }
    static final int[] X = {-2, -1,  1,  2, 2, 1,-1,-2};
    static final int[] Y = {-1, -2, -2, -1, 1, 2, 2, 1};
    
    static int l;
    
    static int[][] graph;

    static Queue<Point> Q = new LinkedList<>();
    
    static void BFS(int startY, int startX, int endY, int endX){

        graph[startY][startX] = 1;
        Q.add(new Point(startY, startX));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            if(y == endY && x == endX) { //목표 정점에 도착하면
                System.out.println(graph[endY][endX] - 1);
                Q.clear(); //큐 비우기
                break;
            }

            for(int a=0; a<8; a++) { //나이트가 갈 수 있는 정점
                int nextY = y + Y[a];
                int nextX = x + X[a];

                if ((nextY >= 0 && nextY < l) && (nextX >= 0 && nextX < l)) //범위 만족
                    if(graph[nextY][nextX] == 0) { //방문한 적 없다면
                        graph[nextY][nextX] = graph[y][x] + 1;
                        Q.add(new Point(nextY, nextX));
                    }

            }
        } //.while()
    }

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

        for(int i=0; i<n; i++){
            l = Integer.parseInt(br.readLine());
            graph = new int[l][l]; //0 ~ l - 1

            int[] arr = new int[4];
            for(int j=0; j<2; j++){
                st = new StringTokenizer(br.readLine());
                arr[j] = Integer.parseInt(st.nextToken());
                arr[j+2] = Integer.parseInt(st.nextToken());
            }
            BFS(arr[0], arr[2], arr[1], arr[3]);
        }
    }
}