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

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

 

16948번: 데스 나이트

 

문제는 시작 지점 (r1, c1)에서 (r2, c2)까지 가는 것인데 갈 때 x좌표 y좌표가

x: {-2, -2, 0, 0, 2, 2}

y: {-1, 1, -2, 2, -1, 1}

이렇게만 움직일 수 있다. 따라서 위 방향대로 움직였을 때 도착지점까지 몇 번 이동을 해야 하는지 구하는 것이다.

 

코드

import java.util.*;

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

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

        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 < 6; 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 -1;
    }
}

 

기존에 풀었던 문제들에서 큰 변형 없이 탈출 조건과 return만 잘 해주면 된다.

만약 nowX와 nowY의 값이 종료지점일 때 카운트++해주고 카운트 값 리턴

아니면 움직여도 도착지점까지 가지 못하면 -1을 리턴해주면 된다.