풀이
나이트의 이동 범위만 정의해주면 쉽게 풀 수 있다…(변수가 많아서 헷갈렸다…)
나이트의 좌표, 이동 횟수 정보는 클래스로 정의하여 큐에 삽입한다. 클래스로 나이트의 정보를 관리할 수 있는 것이 이 문제의 핵심이다.
2차원 배열은 visited 배열만 필요한 것 같다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.*;
public class 나이트의이동 {
static boolean[][] visited;
static int n,nowx,nowy, movex, movey;
//나이트의 이동 범위이다. 근데 이걸 코드 란에 올리면 github 페이지에서 배포 오류가 난다ㅠㅠㅠㅠ대괄호 2개씩 써서 그렇다는데, 이건 너무 하다...그래서 ((로 썼다. 여기서 괄호를 {로 바꿔주면 된다.
//static int[][] move = ((-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2));
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
for (int t = 0 ; t < tc; t++) {
n = sc.nextInt();
nowx = sc.nextInt();
nowy = sc.nextInt();
movex = sc.nextInt();
movey = sc.nextInt();
visited = new boolean[n][n];
bfs(nowx,nowy);
}
}
static void bfs(int x, int y) {
Queue<Night> q = new LinkedList<Night>();
q.add(new Night(x,y, 0));
visited[x][y] = true;
while (!q.isEmpty()) {
Night now = q.poll();
int nx = now.x;
int ny = now.y;
int cnt = now.cnt;
if (nx == movex && ny == movey) {
System.out.println(cnt);
return;
}
for (int i = 0; i < move.length; i++) {
int xx = nx + move[i][0];
int yy = ny + move[i][1];
if (xx >= 0 && yy >= 0 && xx < n && yy < n) {
if (!visited[xx][yy]) {
visited[xx][yy] = true;
q.add(new Night(xx,yy,cnt+1));
}
}
}
}
}
static class Night {
int x, y, cnt;
public Night(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
}
태클 감사합니다.
조언 환영입니다.