반응형
문제
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;
}
}
주의사항
방문체크~!
![](https://t1.daumcdn.net/keditor/emoticon/face/large/071.png)
반응형
'공부 정리 > LeetCode' 카테고리의 다른 글
[LeetCode] happyNumber js (0) | 2023.02.08 |
---|---|
[LeetCode] Min Cost Climbing Stairs 자바 (0) | 2022.06.27 |
[LeetCode] Climbing Stairs (java) (0) | 2022.05.25 |
[LeetCode] Sqrt(x) (java) (0) | 2022.05.25 |
[LeetCode] Add Binary (java) (0) | 2022.05.24 |
댓글