https://www.acmicpc.net/problem/1600
1600번: 말이 되고픈 원숭이
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있
www.acmicpc.net
BFS 문제다.
문제를 해결하기 위해 돌아온 길이 많아서 시행착오는 후에 작성하겠다.
문제 해결은 일반 BFS에 8방향 검사를 추가로 시행했다.
방문 배열을 3차원으로 설정해 8방향 이동 능력을 몇 번 사용했는지 체크했다.
간단한데도 이 방법을 생각해내는데 오래 걸렸다...
그리고 이 문제에서 오류가 발생하기 쉬운 점은 입력이 세로 가로가 아닌 가로 세로인 점이다.
세로를 먼저 입력받는 것이 익숙하기 때문에 m, n으로 입력을 받고 사용은 n, m을 했다.
#include <iostream>
#include <queue>
using namespace std;
int k, n, m;
int board[200][200];
bool visit[200][200][31];
// 상하좌우 탐색을 위함
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };
// 말의 8방향 이동을 위함
int hr[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int hc[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
void BFS() {
// <horse, <r, c>>
queue<pair<int, pair<int, int>>> q;
board[0][0] = 1;
q.push({ 0, { 0, 0 } });
// 큐가 빌 때까지 반복
while (!q.empty()) {
int curr = q.front().second.first;
int curc = q.front().second.second;
int cnt = q.front().first;
q.pop();
// 말의 8방향 이동
if (cnt < k) {
for (int i = 0; i < 8; i++) {
int r = curr + hr[i];
int c = curc + hc[i];
// 범위를 벗어나면 continue
if (r < 0 || c < 0 || r >= n || c >= m) continue;
// 도착지에 도달하면 종료
if (r == n - 1 && c == m - 1) {
cout << board[curr][curc];
return;
}
// 벽이 있다면 continue
if (board[r][c] == -1) continue;
// 방문한 적이 있고 능력을 사용한 횟수가 같다면 continue
if (visit[r][c][cnt + 1]) continue;
board[r][c] = board[curr][curc] + 1;
visit[r][c][cnt + 1] = 1;
q.push({ cnt + 1, { r, c } });
}
}
for (int i = 0; i < 4; i++) {
int r = curr + dr[i];
int c = curc + dc[i];
// 범위를 벗어나면 continue
if (r < 0 || c < 0 || r >= n || c >= m) continue;
// 도착지에 도착하면 종료
if (r == n - 1 && c == m - 1) {
cout << board[curr][curc];
return;
}
// 벽이 있다면 continue
if (board[r][c] == -1) continue;
// 방문한 적이 있고 능력을 사용한 횟수가 같다면 continue
if (visit[r][c][cnt]) continue;
board[r][c] = board[curr][curc] + 1;
visit[r][c][cnt] = 1;
q.push({ cnt, { r, c } });
}
}
cout << -1;
}
int main() {
// 입출력 속도를 단축시키기 위함
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> m >> n;
if (m == n && m == 1) {
cout << 0;
return 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> board[i][j];
if (board[i][j]) board[i][j] = -1;
}
BFS();
}

// 돌고 돌아온 시행착오
처음에는 단순히 4방향 검사 + 말의 8방향 검사를 해주고, 횟수 제한은 이동 수로 체크를 했다.
1
5 2
0 0 0 1 0
0 0 1 0 0
위의 예시가 입력으로 들어온다면 말의 이동 방법은 뒤 쪽에서 장애물을 넘을 때 사용해야 하는데
처음에 생각한 방법으로는 시작하자마자 써버리고 장애물을 넘을 수 없게 된다.
위의 경우를 해결하기 위해 4방향으로 이동했을 때만 방문 체크를 하고
4방향 이동 시 방문한 곳은 들리지 않게 했다.
즉, 8방향으로 이동한 곳에 4방향으로 이동이 가능하게 했다.
3
8 8
0 0 1 1 1 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 1 0 1 1
0 0 1 1 1 0 1 1
0 1 1 0 0 0 1 1
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0
위의 예시는 (0, 1) -> (1, 3) / (4, 3) -> (3, 2) / (5, 0) -> (7, 1) 에서 8방향 이동을 사용해야 한다.
아래 사진은 while문을 돌 때마다 몇 번 째 이동인지 확인한 것이다.
중간 사진에서 (4, 4)의 5는 왼쪽 사진의 (2,5)의 4에서 8방향 이동으로 움직인 것이다.
오른쪽 사진에서 (4, 3)의 6은 (3, 5)의 8방향으로 움직인 것이다.
그 후 같은 자리에 (4, 4)의 5로 인해 다시 6이 된다. 여기서 방문 체크가 된다. (1)
그러나 ㄷ이 뒤집어진 곳에서 이동할 때는 8방향 이동을 하지 않아야 도착할 수 있다.
즉, (1, 5)의 5가 4방향 이동만으로 (4,3)까지 도달해야 한다.
이미 위의 (1)에서 방문 체크가 되었기 때문에 도달할 수 없고 -1이 출력된다.
답은 20이 나와야 한다.



이 외에도 4방향 8방향의 탐색 순서를 바꿔도 값이 달라지기도 했다.
'Algorithm > BFS' 카테고리의 다른 글
| [C++] BOJ(백준) 1938 통나무 옮기기 (0) | 2023.02.15 |
|---|---|
| [C++] BOJ(백준) 2206 벽 부수고 이동하기 (0) | 2023.02.12 |
| [C++] BOJ(백준) 2146 다리 만들기 (0) | 2023.02.05 |
| [C++] BOJ(백준) 4179 불! (0) | 2023.02.03 |
| [C++] BOJ(백준) 2573 빙산 (0) | 2023.02.01 |