알고리즘 공부/백준
[백준] 나이트의 이동(C++/7562번)
dothebest
2021. 5. 6. 11:30
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
코드 설명
BFS기본 틀을 이용하여 풀었다. 출발좌표(sy,sx), 도착좌표(ty,tx) 를 담아줘서 bfs를 돌렸다.
조심해야할점은 최소 몇 번만에 이동하는지 물어봤기 때문에 queue에 cnt+1을 담아줘서 갈수있는 모든방향에 +1을 해주는 식으로 해줘야한다
cnt++을 해주면 모든방향을 ++해주기때문에 답을 찾을 수 없다.
코드
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int map[301][301];
int N;//테스트케이스 개수
bool visited[301][301];
int dy[] = { -2,-2,-1,-1,1,1,2,2 };
int dx[] = { -1,1,-2,2,-2,2,-1,1 };
int bfs(int sy, int sx, int ty, int tx,int a) {
if (sy == ty && sx == tx) {
return 0;
}
queue<pair<pair<int, int>,int>> q;
q.push({ { sy,sx }, 0 });
visited[sy][sx] = true;
while (!q.empty()) {
int y = q.front().first.first;
int x = q.front().first.second;
int cnt = q.front().second;
q.pop();
for (int i = 0; i < 8; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= a || nx >= a) continue;
if (ny == ty && nx == tx) {
return cnt + 1;
}
if (!visited[ny][nx]) {
q.push({{ ny,nx }, cnt + 1
});
visited[ny][nx] = true;
}
}
}
}
int main() {
cin >> N;
vector<int> answer;
for (int i = 0; i < N; i++) {
memset(map, 0, sizeof(map));
memset(visited, false, sizeof(visited));
int cnt = 0;
int a;
cin >> a;
int y, x;
cin >> y >> x;//시작
int ty, tx; //도착
cin >> ty >> tx;
cnt = bfs(y, x,ty,tx,a);
answer.push_back(cnt);
}
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << endl;
}
return 0;
}