[BOJ 7562] 나이트의 이동 (Java)

문제

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

7562번: 나이트의 이동

BOJ 7562

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

풀이

전형적인 BFS 문제.

이동 가능한 좌표를 정의하고 시작한다.

아래 dir을 순회하면서 현재 x좌표에 첫 번째 원소, y좌표에 두 번째 원소를 더하여 다음 좌표를 계산한다.

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

다음 좌표가 valid한지 체크한다. 

    public static boolean isValid(int x, int y, int n, boolean[][] used){
        if(x < 0 || y < 0 || x >= n || y >= n || used[x][y]) return false;
        return true;
    }

Valid하다면 방문 체크를 한 후, queue에 다음 좌표를 넣는다. 

그리고 cnt 를 +1 증가시켜서 넣는다. 

 

x, y 가 목적지일 때의 cnt가 답이 된다.

 

소스코드

package bfs;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ7562 {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] cur = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            st = new StringTokenizer(br.readLine());
            int[] des = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            bw.write(bfs(n, cur, des) + "\n");
        }
        bw.flush();
    }

    public static int[][] dir = {{-1, -2}, {-1, 2}, {-2, -1}, {-2, 1}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
    public static int bfs(int n, int[] cur, int[] des){
        int answer = 0;
        boolean[][] used = new boolean[n][n];
        Queue<Integer> que = new LinkedList<Integer>();
        used[cur[0]][cur[1]] = true;
        que.offer(cur[0]);
        que.offer(cur[1]);
        que.offer(0);

        while(!que.isEmpty()){
            int x = que.poll();
            int y = que.poll();
            int cnt = que.poll();

            if(x == des[0] && y == des[1]){
                answer = cnt;
                break;
            }

            for(int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                if(isValid(nx, ny, n, used)){
                    used[nx][ny] = true;
                    que.offer(nx);
                    que.offer(ny);
                    que.offer(cnt+1);
                }
            }
        }
        return answer;
    }

    public static boolean isValid(int x, int y, int n, boolean[][] used){
        if(x < 0 || y < 0 || x >= n || y >= n || used[x][y]) return false;
        return true;
    }
}