💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 1228KB Time 0ms Code Length 1060B
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
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
using namespace std;
struct point {
int y, x;
};
int main()
{
int t;
scanf("%d", &t);
for (int tc = 1; tc <= t; tc++) {
point start;
point end;
point store[100];
int visited[100]; // 방문한 지점은 방문할 필요가없음.
memset(visited, 0, sizeof(visited));
int n;
scanf(" %d", &n);
scanf(" %d %d", &start.y, &start.x);
for (int i = 0; i < n; i++) {
scanf(" %d %d", &store[i].y, &store[i].x);
}
scanf(" %d %d", &end.y, &end.x);
queue<point> q;
q.push(start);
int flag = 0;
while (!q.empty()) {
point tmp = q.front(); q.pop();
if (abs(end.y - tmp.y) + abs(end.x - tmp.x) <= 1000) {
flag = 1;
break;
}
for (int i = 0; i < n; i++) {
if (visited[i] == 1) continue;
int dist = abs(store[i].y - tmp.y) + abs(store[i].x - tmp.x);
if (dist <= 1000) {
visited[i] = 1;
q.push({ store[i].y, store[i].x });
}
}
}
if (flag) {
printf("happy\n");
}
else {
printf("sad\n");
}
}
}
이 코드는 한 지점에서 다른 지점까지의 이동이 가능한지를 판단하는 프로그램이다. 먼저 시작점과 도착점, 그리고 중간에 있는 여러 지점들의 좌표를 입력받는다. 그리고 시작점부터 도착점까지 이동 가능한 경우 “happy”를 출력하고, 이동이 불가능한 경우 “sad”를 출력한다. 이동 가능 여부는 각 지점 사이의 거리가 1000을 넘지 않는지를 확인하여 결정된다.
