https://www.acmicpc.net/problem/7562
시작점에서 목표 지점까지 최소 경로를 구해야 하므로 BFS를 이용했다.
촌수계산 문제와 비슷하게 최소 횟수를 구해야 하므로, 큐에 (노드, 깊이) 쌍을 저장하기 위해서
노드를 좌표 형태(2차원)가 아니라 1차원 배열 형태로 바꿨다.
그리고 현재 나이트가 놓여있는 칸을 노드 A라고 하면, 다음에 이동할 수 있는 8가지 방향 중에서 체스판 안에 포함되는 칸만 A에 연결된 그래프라고 생각하였다.
#include <iostream>
#include <queue>
using namespace std;
int makePos(int x, int y, int m) {
return x + y * m;
}
vector<int> way(int pos, int l) {
int x = pos % l;
int y = pos / l;
vector<int> v;
int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
int dy[] = {-1, -2, 2, 1, 1, 2, -2, -1};
for(int i=0; i<8; i++) {
int xx = x+dx[i];
int yy = y+dy[i];
if(xx >= 0 && xx < l && yy >= 0 && yy < l) {
v.push_back(makePos(xx, yy, l));
}
}
return v;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, l, cur_x, cur_y, goal_x, goal_y;
cin >> t;
while(t--) {
cin >> l >> cur_x >> cur_y >> goal_x >> goal_y;
int ans = 0;
int cur = makePos(cur_x, cur_y, l);
int goal = makePos(goal_x, goal_y, l);
vector<bool> visited(l*l);
queue<pair<int, int>> q;
q.push({cur, 0});
visited[cur] = true;
while(!q.empty()) {
int pos = q.front().first;
int depth = q.front().second;
q.pop();
if(pos == goal) {
ans = depth;
break;
}
for(int w : way(pos, l)) {
if(!visited[w]) {
q.push({w, depth+1});
visited[w] = true;
}
}
}
cout << ans << "\n";
}
return 0;
}
안녕하세요~! 백준 푸시느라 고생많으셨습니다. 혹시 백준에서 푼 문제를 효율적으로 복습하고 정리하는 데 관심 있으시다면, https://mycodingtest.com 서비스를 한번 이용해보세요! 제가 진행한 개인 프로젝트인데 벨로그에서 백준 푸시는 분들께 댓글로 이렇게 홍보를 하고있습니다. 코테 준비에 도움이 되면 좋겠습니다 😊