Search
Duplicate
📗

현명한 나이트

주차
문제번호
18404
언어
C++
티어
실버
유형
그래프
BFS
nj_Blog
nj_상태
이해도
100%
풀이
사람
이해도 2
13 more properties

문제접근

나이트의 위치에서 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); }
C++
복사