[LeetCode] 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.

 

 

 

 

 

---

문제[번역]

 

 

무한으로 늘어나는 체스판에서, [0,0]인 지점에서 말을 놓습니다.

나이트는 그림처럼 8칸으로 이동가능합니다.

x,y가 주어질때 몇번만에 도달 가능한가요?

 

 

 

---

 

Example 1

0

0

 

0

Example 2

2

112

 

56

 

 

 

 

 

---

제약조건

 

 

• -300 <= x, y <= 300
• 0 <= |x| + |y| <= 300

 

 

 

 

---

접근방법

 

BFS를 이용하면 문제를 풀 수 있으나, 방문체크를 안해주고 그냥 BFS만 돌리면 시간초과가 납니다.

 

 

---

코드

 

class Solution {
  static int dx[]={2,-2,-2,2,1,1,-1,-1};
  static int dy[]={1,-1,1,-1,2,-2,2,-2,};
    public int minKnightMoves(int x, int y) {
      Queue<int[]> q = new LinkedList<>();
      q.add(new int[]{0,0,1});
      boolean visit[][] = new boolean[601][601];
      if(x==0 && y==0) return 0;
      while(!q.isEmpty()){
        int cur[] = q.poll();
        int cx = cur[0];
        int cy = cur[1];
        int cc = cur[2];
        
        for(int i=0; i<8; i++){
          int nx = cx + dx[i];
          int ny = cy + dy[i];
          if(visit[nx+300][ny+300]) continue;
          if(nx == x && ny == y){
            return cc;
          }
          else{
            q.add(new int[]{nx,ny,cc+1});
            visit[nx+300][ny+300] = true;
          }
        }
      }
      return 0;
    }
}

 

 

---

주의사항

 

방문체크~!