bfs를 이용한 문제이다. 간단한 bfs 구현 문제로 문제에서 주어진 이동 조건을 dy
, dx
로 구현해 풀어주었다.
쉽게 풀 수 있었던 문제였다. 다만 오타로 인해 시간 낭비가 좀 있었다. 오타를 찾지 못해 시간을 허비하는 경우가 잦은 것 같다. 오타를 줄이도록 노력하자.
#include <iostream>
#include <queue>
using namespace std;
int N, result = -1;
int r1, c1, r2, c2;
int dy[6] = { -2,-2,0,0,2,2 };
int dx[6] = { -1,1,-2,2,-1,1 };
bool check[200][200];
void bfs() {
queue<pair<pair<int, int>, int>> q;
q.push({ {r1,c1},0 });
check[r1][c1] = true;
while (!q.empty()) {
int y = q.front().first.first;
int x = q.front().first.second;
int count = q.front().second;
if (y == r2 && x == c2) {
result = count;
break;
}
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 (check[ny][nx]) continue;
q.push({ {ny,nx},count + 1 });
check[ny][nx] = true;
}
}
}
void solution() {
bfs();
cout << result;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
cin >> r1 >> c1 >> r2 >> c2;
solution();
return 0;
}