백준 16948번 - 데스나이트

코드

public class Baekjoon16948 {

    static int[] arrx = new int[]{-2, -2, 0, 0, 2, 2};
    static int[] arry = new int[]{-1, 1, -2, 2, -1, 1};

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

        boolean[][] visited = new boolean[N + 1][N + 1];

        int fx = sc.nextInt();
        int fy = sc.nextInt();
        Point start = new Point(fx, fy, 0);

        int sx = sc.nextInt();
        int sy = sc.nextInt();
        Point end = new Point(sx, sy, 0);

        Queue<Point> queue = new LinkedList<>();
        queue.offer(start);
        visited[fy][fx] = true;

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            if (current.equals(end)) {
                System.out.println(current.getCount());
                return;
            }


            for (int i = 0; i < arrx.length; i++) {
                int nx = arrx[i] + current.getX();
                int ny = arry[i] + current.getY();

                if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[ny][nx]) {
                    continue;
                }

                Point point = new Point(nx, ny, current.count + 1);
                queue.offer(point);
                visited[ny][nx] = true;

            }
        }

        System.out.println(-1);


    }

    static class Point {
        private int x;
        private int y;
        private int count;

        public Point(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return getX() == point.getX() && getY() == point.getY();
        }

        @Override
        public int hashCode() {
            return Objects.hash(getX(), getY());
        }
    }
}

풀이

😎bfs의 개념에 대해서 알고있다면 쉽게 풀 수 있는 문제이다.

1. 갈 수 있는 방향에 대하여 arrx,arry의 배열로 저장
2. 입력 받은 값을 start로 저장한 후 queue에 저장
3. queue가 empty할 때 까지 while문을 돌린다. while문에서는 queue의 값을 꺼내어 해당 값이 목적지(end)라면 return; 하여 끝낸다 아니라면 다음 point로 이동
4. for문을 통해 다음 장소로 이동 시킨다. 이 때 arrx, arry에서 값을 하나씩 꺼내어 현재 값에 더하여 다음 장소를 구한다. 이 때 지정 범위를 넘어간다면 continue; 아니라면 queue의 저장한다. 이 때 visited 배열을 true로 만들어준다.
5. end에 도달하지 못한 경우 -1을 출력한다.

🫠위에서 visited배열을 생성한 이유는 이미 방문한 배열의 경우 방문하지 않게 하여 queue의 들어가는 값을 줄이려고 한 것이다. 또한 Point의 equals 와 hashcode를 재정의 하였는데 count를 빼고 재정의 해줘야 제대로 작동한다.(사실 직접 값을 비교해줘도 되지만 IDE를 통해 쉽게 생성할 수 있어서 재정의해주었다.)

출처 : 백준 - 데스나이트