문제
https://www.acmicpc.net/problem/7562
풀이
너비 우선 탐색
간단한 BFS 문제로 기존 문제와 다른 점은 목적지에 도착할 때까지 걸린 count가 필요하다.
- bool 배열로 해당 칸의 방문 여부를 판별하는 것보다 int 배열로 해당 칸에 도착할 때까지 걸린 count를 기록한다.
- 방문 여부는 해당 칸의 count가 0인지를 확인하면 된다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
int T;
int I;
// visited 배열이 아닌 int로 count와 방문 여부를 동시 관리
int moveCount[300][300];
int moveX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int moveY[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> T;
memset(moveCount, 0, sizeof(moveCount));
while (T--)
{
int startX, startY, destX, destY;
queue<pair<int, int>> q;
cin >> I;
cin >> startX >> startY >> destX >> destY;
q.push(make_pair(startX, startY));
while (false == q.empty())
{
int currentX = q.front().first;
int currentY = q.front().second;
q.pop();
if (destX == currentX && destY == currentY)
{
cout << moveCount[currentX][currentY] << '\n';
break;
}
for (int i = 0; i < 8; ++i)
{
int nextX = currentX + moveX[i];
int nextY = currentY + moveY[i];
// moveCount가 0이 아닌 경우는 이미 방문한 칸이므로 continue 처리
if (nextX < 0 || nextX >= I || nextY < 0 || nextY >= I || 0 != moveCount[nextX][nextY])
{
continue;
}
q.push(make_pair(nextX, nextY));
moveCount[nextX][nextY] = moveCount[currentX][currentY] + 1;
}
}
memset(moveCount, 0, sizeof(moveCount));
}
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 9020: 골드바흐의 추측 (0) | 2024.05.06 |
---|---|
[백준][C++] 1065: 한수 (0) | 2024.05.04 |
[백준][C++] 2512: 예산 (0) | 2024.04.29 |
[백준][C++] 14888: 연산자 끼워넣기 (0) | 2024.04.21 |
[백준][C++] 17143: 낚시왕 (1) | 2024.04.21 |