https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ...
www.acmicpc.net
위의 그림은 체스에서 나이트가 이동할 수 있는 위치를 나타낸다.
시작 위치로부터 도착 위치까지 나이트가 몇 번 움직이면 도착할 수 있는지를 구하는 문제이다.
bfs로 쉽게 최소 이동 횟수를 구해줄 수 있다.
먼저 시작 위치와 도착 위치가 같은 경우 0을 출력하고 다음 테스트 케이스로 넘어가도록 처리해준다.
그렇지 않다면 bfs로 이동을 시작한다.
현재 좌표에서 나이트가 이동할 좌표를 미리 다음과 같이 만들어 놓는다.
int dx[] = {-2,-2,-1,-1,1,1,2,2};
int dy[] = {-1,1,-2,2,-2,2,-1,1};
단계별로 진행하기 위해 큐의 사이즈를 미리 저장해놓고 큐의 사이즈만큼 탐색을 진행한다.
그리고 탐색이 끝날 때마다 count값을 증가시킨다.
도착점에 도착했다면 탐색을 마치고 바로 count값을 출력한다.
|
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n;
int sx, sy;
int ex, ey;
bool check[300][300];
//나이트가 이동할 수 있는 위치
int dx[] = {-2,-2,-1,-1,1,1,2,2};
int dy[] = {-1,1,-2,2,-2,2,-1,1};
void bfs() {
memset(check, false, sizeof(check));
queue<pair<int, int>> q;
q.push(make_pair(sx,sy));
check[sx][sy] = true;
int count = 0;
while (!q.empty()) {
int qsize = q.size();
while (qsize-- > 0) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 8; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (check[nx][ny]) continue;
q.push(make_pair(nx, ny));
check[nx][ny] = true;
}
}
count++;
//도착 위치에 도착한 경우 탐색 중단
if (check[ex][ey]) {
break;
}
}
//이동 횟수 출력
cout << count << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> n;
cin >> sx >> sy;
cin >> ex >> ey;
//시작위치와 도착위치가 같은 경우 0을 출력하고 다음 테스트케이스 진행
if (sx == ex && sy == ey) {
cout << 0 << '\n';
continue;
}
bfs();
}
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 11723. 집합 (0) | 2019.07.11 |
|---|---|
| [BOJ] 1987. 알파벳 (0) | 2019.07.11 |
| [BOJ] 2638. 치즈 (0) | 2019.07.08 |
| [BOJ] 2636. 치즈 (0) | 2019.07.08 |
| [BOJ] 1347. 미로 만들기 (0) | 2019.07.06 |