💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 1580KB Time 20ms Code Length 996B
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
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
struct info {
int y, x, cnt;
};
int dy[] = { -2,-2,-1,-1,1,1,2,2 };
int dx[] = { 1,-1,-2,2,-2,2,1,-1 };
int visited[301][301];
void init() {
memset(visited, 0, sizeof(visited));
}
int main() {
int tc;
int l;
info start, end;
scanf("%d", &tc);
for (int T = 1; T <= tc; T++) {
init();
start.cnt = 0;
scanf(" %d", &l);
scanf(" %d %d", &start.y, &start.x);
scanf(" %d %d", &end.y, &end.x);
queue<info> q;
q.push(start);
visited[start.y][start.x] = 1;
int result = 0;
while (!q.empty()) {
info tmp = q.front(); q.pop();
if (tmp.y == end.y && tmp.x == end.x) {
result = tmp.cnt;
break;
}
for (int i = 0; i < 8; i++) {
int ny = tmp.y + dy[i];
int nx = tmp.x + dx[i];
if (ny >= l || nx >= l || nx < 0 || ny < 0) continue;
if (visited[ny][nx] == 1) continue;
visited[ny][nx] = 1;
q.push({ ny, nx, tmp.cnt + 1 });
}
}
printf("%d\n", result);
}
}
이 코드는 나이트의 이동 경로를 구하는 문제를 해결하는 프로그램이다.
먼저, 입력으로 테스트 케이스의 개수를 받고, 각 테스트 케이스마다 시작점과 도착점의 좌표를 입력받는다.
그 후, 방문한 위치를 표시하기 위한 visited 배열을 초기화하고, 시작점을 큐에 넣고 방문했음을 표시한다.
큐가 빌 때까지 다음을 반복한다: 큐에서 하나의 위치를 꺼내서 해당 위치가 도착점인지 확인하고, 아니라면 나이트의 이동 가능한 8가지 방향을 확인하여 갈 수 있는 위치를 큐에 넣고 방문했음을 표시한다.
도착점에 도달하면 해당 위치까지의 이동 횟수를 결과로 저장하고 반복을 종료한다.
마지막으로 결과를 출력한다.
