[BFS] 백준 - 7562번: 나이트의 이동 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

7562번: 나이트의 이동

 

 

이 문제는 나이트가 특정 좌표로 이동하는 데까지 몇 번 움직이는지 출력하는 건데 나이트는 다음과 같이 움직인다.

 

static int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
static int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

 

이 문제를 보니 바로

[BFS] 백준 - 16948번: 데스 나이트 Java 풀이

이 포스팅에서 푼 문제와 비슷한 문제여서 dx, dy와 테스트케이스만큼 돌리는 것을 수정해주면 바로 맞는 문제였다.

 

코드

import java.util.*;

public class Main {
    static boolean[][] map;
    static int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
    static int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    static int n;
    static int ex;
    static int ey;

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

        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            n = sc.nextInt();
            map = new boolean[n][n];

            int sx = sc.nextInt();
            int sy = sc.nextInt();
            map[sx][sy] = true;

            ex = sc.nextInt();
            ey = sc.nextInt();
            map[ex][ey] = true;

            System.out.println(bfs(sx, sy));
        }
    }

    private static int bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y, 0});
        boolean[][] visit = new boolean[n][n];
        visit[x][y] = true;

        while (!q.isEmpty()) {
            int[] list = q.poll();
            int cx = list[0];
            int cy = list[1];
            int cc = list[2];

            for (int i = 0; i < 8; i++) {
                int nowX = cx + dx[i];
                int nowY = cy + dy[i];
                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < n) {
                    if (!visit[nowX][nowY]) {
                        if (nowX == ex && nowY == ey) {
                            cc++;
                            return cc;
                        } else {
                            visit[nowX][nowY] = true;
                            q.add(new int[]{nowX, nowY, cc + 1});
                        }
                    }
                }
            }
        }
        return 0;
    }
}

 

거저먹었다..