[DFS/BFS] 백준 7562번 나이트의 이동(Java)

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

7562번: 나이트의 이동

📚 문제

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

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다.둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

예제 입력	예제 출력
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1	5 28 0

 

📝 문제 해결

1) 나이트가 움직일 수 있는 방향 8개를 배열로 선언
2) 시작점에서 1) 배열값을 더해준 뒤 이동할 좌표가 범위 내이고 아직 방문하지 않았다면 이동 & 거리값을 업데이트
3) 끝점에 도착하는 순간 탈출 & 해당 좌표값 return

 

💻 코드

package BOJ;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class No7562 {
    static int col, goalX, goalY;
    static int map[][];
    static boolean visited[][];
    static int[] dx = {-2, -1, 1, 2, 2, 1 ,-1, -2};
    static int[] dy = {-1, -2, -2, -1, 1 ,2 ,2, 1};

    public static void bfs(int x, int y){
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{x,y});
        visited[x][y] = true;

        while(!que.isEmpty()){
            int[] now = que.poll();

            if(now[0] == goalX && now[1] == goalY) break;

            for(int i=0; i<8; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];

                if(0<=nx && nx<col && 0<=ny && ny<col && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    map[nx][ny] = map[now[0]][now[1]] + 1;
                    que.add(new int[]{nx,ny});
                }
            }
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int t=0; t<T; t++) {
            col = sc.nextInt();
            map = new int[col][col];
            visited = new boolean[col][col];

            int x = sc.nextInt();
            int y = sc.nextInt();

            goalX = sc.nextInt();
            goalY = sc.nextInt();

            bfs(x, y);
            System.out.println(map[goalX][goalY]);
        }
    }
}