18404번: 현명한 나이트

문제접근🤔

• 나이트의 위치에서 bfs를 돌려 각 칸마다 가는 횟수를 기록해둔다
• 각 케이스에 대해 바로 접근하여 출력

놓쳤던 부분😅

• 각 케이스마다 bfs를 돌며 찾으려고 했는데 bfs를 한번 돌리고 그 위치까지 얼마나 걸리는지 찾는게 더 간단함

코드😁

3084 KB

12 ms

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

vector<vector<int> > board;
int input1, input2;
int n, m;

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

void bfs(int row, int col) {
	queue<pair<int, int> > q;

	q.push({row, col});
	board[row][col] = 0;

	while (!q.empty()) {
		int currentRow = q.front().first;
		int currentCol = q.front().second;

		q.pop();
		for (int i = 0; i < 8; i++) {
			int nextRow = currentRow + dy[i];
			int nextCol = currentCol + dx[i];

			if (nextRow <= 0 || nextRow > n || nextCol <= 0 || nextCol > n)
				continue ;
			if (board[nextRow][nextCol] != -1)
				continue ;
			board[nextRow][nextCol] = board[currentRow][currentCol] + 1;
			q.push({nextRow, nextCol});
		}
	}
}

int main(void) {
	int knightRowPosition, knightColPosition;

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	cin >> knightRowPosition >> knightColPosition;

	board.resize(n + 1, vector<int>(n + 1, -1));

	bfs(knightRowPosition, knightColPosition);
	for (int i = 0; i < m; i++) {
		cin >> input1 >> input2;
		cout << board[input1][input2] << " ";
	}
	return (0);
}