[백준] 7562 나이트의 이동 자바 BFS 문제 풀이 및 정답

문제 요약)

- 나이트의 위치가 주어지고 8방향으로 이동이 가능

- 시작점부터 도착지점까지의 이동 거리 출력

 

주의점)

- 8방향 좌표만 잘 기억하면 큰 어려움 x

 

풀이)

보통은 4방향 탐색을 많이 하는데 약간 응용해서

8방향으로 탐색을 하는 문제이기에 방향만 잘 정해서

8방향 탐색루프를 돌며 bfs 진행

 

정답)

*Scanner 대신 bufferedReader를 사용하면 시간을 더 줄일 수 있습니다.

import java.util.*;

public class KnightMove7562_blog {
    static int[] dx = {-1, -2, -2, -1, 1, 2, 2, 1}; // 8방향 탐색
    static int[] dy = {-2, -1, 1, 2, 2, 1, -1, -2};
    static int t;
    static int n;
    static int[][] map;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        
        for (int i = 0; i< t; i++) {
            n = sc.nextInt();
            map = new int[n][n];

            int beginX = sc.nextInt();
            int beginY = sc.nextInt();

            int endX = sc.nextInt();
            int endY = sc.nextInt();

            BFS(beginX, beginY);
            System.out.println(map[endX][endY] - 1); // 1로 시작했기 때문에 -1 해주기
        }
    }

    static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y});
        map[x][y] = 1; // 1로 해줘야 방문한곳 판단이 쉬워서

        while(!q.isEmpty()) {
            int[] current = q.poll();
            for (int i=0; i<dx.length; i++) {
                int nextX = current[0] + dx[i];
                int nexY = current[1] + dy[i];

                // out of index 방지, 이미 방문한 곳 제외
                if (nextX < 0 || nextX >= n || nexY < 0 || nexY >= n) continue;
                if (map[nextX][nexY] > 0) continue;

                q.offer(new int[] {nextX, nexY});
                map[nextX][nexY] = map[current[0]][current[1]] + 1;
            }
        }
    }
}