[백준-7562번 자바/java] 나이트의 이동 _디버깅의 눈물
https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
나이트의 이동 성공다국어
| 1 초 | 256 MB | 41290 | 20808 | 15578 | 49.402% |
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
예제 입력 1 복사
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
예제 출력 1 복사
5
28
0
체크 포인트
1. 너비 우선 탐색(BFS) 문제
-나이트가 목표지점까지 '최소 몇번의 이동'으로 움직일 수 있는지를 찾는 문제
2. 나이트의 이동방향 설정
// 나이트 이동 방향
static int[] dx = {-2,-2,-1,-1,1,1,2,2};
static int[] dy = {-1,1,-2,2,-2,2,-1,1};
3. 나이트의 현재 칸/나이트의 이동목표 칸의 구분
-기준점 = 나이트의 현재 위치
-목표점 = 나이트가 최종 이동해야할 위치
// 기준점
if(i==0){
map[a][b] = 1;
// 기준점을 큐에 넣어준다.
Q.add(new Integer[]{a,b});
}
// 목표점
else{
map[a][b] = -1;
}
4. 나이트의 이동거리 계산
// 방문했던 적이 없는 곳이면,
if(map[nx][ny]==0){
// 방문 처리(이동수 +1 처리)
map[nx][ny] = map[x][y] + 1;
// (nx,ny)에서 BFS 탐색 시작을 위한 추가
Q.add(new Integer[]{nx,ny});
}
-새로운 map[nx][ny]의 값을 이전 map[n][y]의 값에 + 1로 처리하여, 이전보다 한칸 더 이동했음을 표시
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 테스트 케이스의 가지수 T, 체스판 한변의 길이 I
static int T,I;
// 체스판 배열
static int[][] map;
// 나이트 이동 방향
static int[] dx = {-2,-2,-1,-1,1,1,2,2};
static int[] dy = {-1,1,-2,2,-2,2,-1,1};
static Queue<Integer[]> Q;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 테스트 케이스
T = Integer.parseInt(st.nextToken());
for(int k=0; k<T; k++){
st = new StringTokenizer(br.readLine());
// 체스판 한변의 길이
I = Integer.parseInt(st.nextToken());
// 배열 초기화
map = new int[I][I];
// 큐 초기화
Q = new LinkedList<Integer[]>();
// 두 점의 위치 정보 입력
for(int i=0; i<2; i++){
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 기준점
if(i==0){
map[a][b] = 1;
// 기준점을 큐에 넣어준다.
Q.add(new Integer[]{a,b});
}
// 목표점
else{
map[a][b] = -1;
}
}
// BFS 탐색 시작
BFS();
}
}
static void BFS() {
while(!Q.isEmpty()){
Integer[] temp = Q.poll();
int x = temp[0];
int y = temp[1];
// 나이트의 이동 구간 탐색
for(int i=0; i<8; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 체스판 위에 존재하고,
if(nx>=0 && ny>=0 && nx<I && ny<I){
// 방문했던 적이 없는 곳이면,
if(map[nx][ny]==0){
// 방문 처리(이동수 +1 처리)
map[nx][ny] = map[x][y] + 1;
// (nx,ny)에서 BFS 탐색 시작을 위한 추가
Q.add(new Integer[]{nx,ny});
}
// 목표점에 도달했다면,
else if(map[nx][ny]==-1){
// 결과 출력
System.out.println(map[x][y]);
return;
}
}
}
}
} // end of BFS
} // end of Main