데스 나이트(16948)

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

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 NxN인 체스판과 두 칸(r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다. 데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5≤N≤200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c2)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

예제 입력 1

7
6 6 0 1

예제 출력 1

4

예제 입력 2

6
5 1 0 5

예제 출력 2

-1

예제 입력 3

7
0 3 4 3

예제 출력 3

2

풀이

기본적인 BFS 문제였기 떄문에 그렇게 어려운 점은 딱히 없었지만 조금 막혔던 부분은 역시 출력하는 부분인데, 이걸 for문 내에서 돌리고 있어서 조금은 문제를 겪었지만 이걸 for문 돌기 전에 값을 꺼냈을때로 바꾸니까 성공했다!!

→ 이유는 결국 for문 안에서는 마지막 점을 찾고나서 +해주는 과정을 거쳐야 원하는 값이 나오는데 기존에 for문 안에서 찾는 과정을 진행하게되면 +을 하기 전에 결과값을 출력해버리기 때문에 1에 문제가 생겼었다..! 간단했다!!

import java.util.*;
import java.io.*;
public class Main{
    static int n;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {-2, -2, 0, 0, 2, 2};
    static int[] dy = {-1, 1, -2, 2, 1, -1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        visited = new boolean[n][n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int sx = Integer.parseInt(st.nextToken());
        int sy = Integer.parseInt(st.nextToken());
        int ex = Integer.parseInt(st.nextToken());
        int ey = Integer.parseInt(st.nextToken());

        fn(sx, sy, ex, ey);
    }

    public static void fn(int sx, int sy, int ex, int ey){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sx, sy});
        visited[sx][sy] = true;

        while(!q.isEmpty()){
            int[] xy = q.poll();
            if(xy[0]==ex && xy[1]==ey){
                System.out.println(arr[xy[0]][xy[1]]);
                return;
            }
            for(int i=0; i<6; i++){
                int nx = xy[0] + dx[i];
                int ny = xy[1] + dy[i];
                if(nx<0 || nx>=n || ny<0 || ny>=n || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                q.add(new int[] {nx, ny});
                arr[nx][ny] = arr[xy[0]][xy[1]] + 1;
            }
        }
        System.out.println(-1);
    }
}