[Leetcode] 1197. Minimum Knight Moves

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:

Input: x = 2, y = 1 Output: 1 Explanation: [0, 0] → [2, 1]

Example 2:

Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

Constraints:

• |x| + |y| <= 300

 

BFS 로 찾을 수 있다. 하지만 그냥 BFS 를 수행했을시, TLE 에 걸리게 되며 1사분면만 찾도록 하는 최적화를 했더니 통과가 되었다.

 

더 빠른 DP 솔루션도 있는듯 하나.. 이 부분은 나중에 시간되면 봐야지.. 패스!

import java.util.*;

public class MinimumKnightMoves {
    static int [][] directions = {
        {-2, -1},
        {-2, 1},
        {-1, -2},
        {-1, 2},
        {1, -2},
        {1, 2},
        {2, -1},
        {2, 1}
    };

    public int minKnightMoves(int x, int y) {
        // 1사분면만 탐색하게 해준다.
        x = Math.abs(x);
        y = Math.abs(y);

        Point start = new Point(0, 0);

        Set<Point> visited = new HashSet<>();
        visited.add(start);

        Queue<Point> q = new LinkedList<>();
        q.add(start);

        int step = 0;

        while (q.isEmpty() == false) {
            int size = Integer.valueOf(q.size());

            for (int i = 0; i < size; i++) {
                Point point = q.poll();

                if (point.y == y && point.x == x) {
                    return step;
                }

                for (int [] dir : directions) {
                    Point next = new Point(point.y + dir[0], point.x + dir[1]);

                    // For example, to reach (1,1) from (0, 0), the best way is to get (2, -1) or (-1, 2) first, then (1,1) (two steps).
                    // If we eliminate all coordinates with negative numbers, then we can't reach (1,1) from (0, 0) within two steps.
                    if (visited.contains(next) == false && next.y >= -1 && next.x >= -1) {
                        q.add(next);
                        visited.add(next);
                    }
                }
            }

            step++;
        }

        return -1;
    }


    static class Point {
        int y;
        int x;

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

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

        @Override
        public int hashCode() {
            return Objects.hash(y, x);
        }
    }
}