[백준 알고리즘]/[C++]
16948번 데스 나이트 | BFS | 백준 16948 C++ 코드
말하는펭귄
2021. 2. 24. 19:04
728x90
반응형
이번 포스팅은 백준 16948번 데스 나이트입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
16948번: 데스 나이트
게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크
www.acmicpc.net
기본 알고리즘
최단 경로 = BFS (너비 우선 탐색)
참고
체스판의 행과 열은 0번부터 시작한다.
전체 코드
|
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
|
//백준16948 데스 나이트
#include <iostream>
#include <queue>
using namespace std;
int N;
const int MAX = 201;
int path[MAX][MAX];
bool visited[MAX][MAX];
queue<pair<int, int>> q;
int dy[] = {-1,1,-2,2,-1,1};
int dx[] = {-2,-2,0,0,2,2};
void BFS(int y, int x) {
path[y][x] = 0;
visited[y][x] = true;
q.push(make_pair(y, x));
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int i = 0; i < 6; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny > N || nx > N)
continue;
if (!visited[ny][nx]) {
visited[ny][nx] = true;
path[ny][nx] = path[y][x] + 1;
q.push(make_pair(ny, nx));
}
}
}
}
int main() {
cin >> N;
int a, b, c, d; //r1 c1 r2 c2
cin >> a >> b >> c >> d;
BFS(b, a);
if (path[d][c] == 0)
cout << -1;
else
cout << path[d][c];
}
|
cs |
728x90
반응형