백준/bfs, dfs
(c++)백준 16948번: 데스 나이트
Nimgnoej
2020. 8. 29. 16:51
https://www.acmicpc.net/problem/16948
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를 사용했다.
데스 나이트가 있는 칸에서 6방향을 모두 살펴보며 칸을 이동할 때마다 전 칸까지의 이동 횟수 + 1을 저장해둔다.
#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;
struct pos {
int r, c;
};
int N;
int r1, c1;
int r2, c2;
int visited[200][200];
const int dxy[][2] = { {-2,-1},{-2,1},{0,-2},{0,2},{2,-1},{2,1} };
void bfs() {
queue<pos>q;
q.push({ r1,c1 });
visited[r1][c1] = 0;
while (!q.empty()) {
int r = q.front().r;
int c = q.front().c;
q.pop();
for (int i = 0; i < 6; i++) {
int nr = r + dxy[i][0];
int nc = c + dxy[i][1];
if (nr < 0 || nr >= N || nc < 0 || nc >= N)
continue;
if (visited[nr][nc] == -1 || (visited[nr][nc] > visited[r][c] + 1)) {
visited[nr][nc] = visited[r][c] + 1;
q.push({ nr,nc });
}
}
}
}
int main() {
cin >> N;
cin >> r1 >> c1 >> r2 >> c2;
memset(visited, -1, sizeof(visited));
bfs();
cout << visited[r2][c2] << '\n';
return 0;
}