백준 7562번 나이트의 이동 C++ BFS

리뷰

나이트가 출발지로 부터 도착지까지 이동하는 최단거리는 구하는 문제

 

문제 풀이

1. 나이트가 이동할 수 있는 방향 배열을 만들어 주고, 현재의 위치와 이동 시간을 체크할 구조체를 만들어 준다.
2. 각 테케마다 출발지와 도착지를 입력 받고 bfs를 시작한다. 큐에 시작 위치를 추가하고 방문 체크용 2차배열을 만든다.
3. while루프를 시작하고 현재 위치가 도착지라면 이동 시간을 리턴, 출력해 주면 된다.

 

참고 사항

int dirx[] = { -1, -2, -2, -1, 1, 2, 2, 1};
int diry[] = { -2, -1, 1, 2, 2, 1, -1, -2};

방향 배열은 위와 같다.

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int tc, n, sx, sy, dx, dy;

int dirx[] = { -1, -2, -2, -1, 1, 2, 2, 1};
int diry[] = { -2, -1, 1, 2, 2, 1, -1, -2};

struct Pos {
	int x, y, t;
};

int bfs(Pos pos) {
	queue<Pos> q;
	q.push(pos);
	vector<vector<int>> v(n, vector<int>(n, 0));
	v[pos.x][pos.y] = 1;

	while (!q.empty()) {
		Pos now = q.front();
		q.pop();
		int x = now.x, y = now.y, t = now.t;
		if (x == dx && y == dy) return t;
		for (int i = 0; i < 8; i++) {
			int nx = x + dirx[i], ny = y + diry[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !v[nx][ny]) {
				v[nx][ny] = 1;
				q.push({ nx, ny, t + 1 });
			}
		}
	}
}

int main() {
	cin >> tc;
	while (tc--) {
		cin >> n;
		cin >> sx >> sy >> dx >> dy;
		cout << bfs({ sx, sy, 0 }) << "\n";
	}
}