백준 7562 나이트의 이동

문제 링크 : https://www.acmicpc.net/problem/7562

※선행해야 할 알고리즘 : BFS/DFS

Algorithm : I크기의 체스판에서 시작점부터 종료점까지 나이트의 이동거리를 출력하시오.

1. I*I크기의 체스판에서 시작점과 종료점을 준 후 나이트의 이동거리를 T개 구하는 문제이다.

가장 먼저 해야할 일은

나이트의 8개 이동방향을 코드로 작성하는 것이다.

BFS를 진행 할 시 모든 이동방향을 고려하여 queue에 삽입 후 종료점을 만났을 때 return하기 때문이다.

따라서, 해당 코드를 작성하면 아래와 같다.

int dy[] = { 1, 1, -1, -1, 2, 2, -2, -2 };

int dx[] = { -2, 2, -2, 2, -1, 1, -1, 1 };

2. 또한 입력 시 시작점을 바로 queue에 삽입 후 dx, dy를 기준으로 BFS를 진행하면 된다.

3. 1~2를 queue를 활용하여 T번 반복하여 BFS를 진행하면 다음과 같다.

//kuklife.tistory.com #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; int dy[] = { 1, 1, -1, -1, 2, 2, -2, -2 }; int dx[] = { -2, 2, -2, 2, -1, 1, -1, 1 }; typedef struct set { int y, x, count; }set; int sol(pair<int, int> F, queue<set> q, int I, vector<vector<bool>>visit) { int result = 0; while (!q.empty()) { int y = q.front().y; int x = q.front().x; int count = q.front().count; q.pop(); visit[y][x] = true; result = count; if (y == F.first && x == F.second) break; for (int i = 0; i < 8; i++) { int now_y = y + dy[i]; int now_x = x + dx[i]; if (now_y >= 0 && now_y < I && now_x >= 0 && now_x < I && !visit[now_y][now_x]) { q.push({ now_y, now_x ,count + 1 }); visit[now_y][now_x] = true; } } } return result; } int main() { int T; cin >> T; vector<int> N; pair<int, int> start, finish; for (int i = 0; i < T; i++) { int I; queue<set>q; cin >> I; vector<vector<bool>>visit(I); for (int j = 0; j < I; j++) visit[j].resize(I, false); cin >> start.first >> start.second; q.push({ start.first, start.second, 0 }); cin >> finish.first >> finish.second; N.push_back(sol(finish, q, I, visit)); } for (int i = 0; i < N.size(); i++) cout << N[i] << endl; return 0; }