1. 문제 이해
2차원 배열 위에서 원숭이가 이동하는 문제이다. 원숭이는 말 처럼 이동할 수 있는데 체스의 나이트처럼 이동할 수 있다. 단, 말 처럼 이동할 수 있는 횟수는 K번이다. 그 외에는 상하좌우 로만 이동가능하다.
원숭이가 (0,0) 좌표에서 (h-1, w-1) 좌표로 이동할 떄, 최소한의 이동횟수를 구하는 문제이다.
2. 문제 풀이
말의 이동횟수를 제외하고 생각한다면 간단한 BFS 문제이다. 간단한 BFS 문제에서 한 번 방문했던 곳을 다시 방문하는 문제를 해결하기 위해, 방문 여부를 체크하는 방법을 사용한다. 특정 좌표를 이미 방문한 적이 있다면 같은 결과를 도출해 내기 때문에 다시 방문할 필요가 없다.
이 문제에서도 똑같이 방문 여부를 체크해야 한다. 그러나, 같은 결과를 도출해내는 방문만 걸러야 한다. 방문을 할 때 가지고 있는 정보는 총 3가지이다.
가로좌표, 세로좌표, 이동횟수
이동횟수에도 종류가 있다. 총 이동횟수와 말 처럼 이동할 수 있는 횟수. 이 때, 같은 결과를 도출해 낼 수 있는 횟수는 말 처럼 이동할 수 있는 횟수이다. 총 이동횟수는 정답이기 때문에 말 처럼 이동할 수 있는 횟수를 검사해야 한다.
검사하는 방법은 간단하게 3차원 배열을 사용하면 된다. 방문여부만 체크할 때는 2가지 변수, 가로와 세로만 검사해서 2차원 배열로 충분했지만, 말 처럼 이동할수 있는 횟수의 변수가 하나 추가되었기 때문에 3차원 배열을 사용해야 한다
말 처럼 이동할 수 있는 횟수는 최대 30으로 작기 때문에 메모리 문제도 없다.
3. 문제 예제
더보기
3
4 5
0 1 1 1
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 0
답:3
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
답:20
1
4 4
0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0
답: 4
1
5 5
0 1 1 0 1
0 0 1 0 1
0 1 0 1 1
0 1 0 1 0
1 1 0 1 0
답: -1
0
5 3
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
답: 10
1
4 4
0 1 1 1
0 0 1 1
1 0 1 1
1 1 1 0
정답 : 4
5
6 6
0 0 0 0 0 1
0 0 0 1 0 1
0 1 0 0 0 1
0 1 0 0 1 0
0 0 0 0 0 1
1 0 0 0 1 0
답: 4
2
5 3
0 0 0 0 0
1 0 1 1 0
1 0 1 1 0
답: 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
답: 20
1
4 4
0 0 1 1
0 0 1 1
0 0 1 1
1 1 1 0
답: 4
5
1 1
0
답: 0
1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0
답: 6
1
3 4
0 0 0
1 1 0
1 1 1
1 0 0
답: 5
4
6 10
0 0 1 1 1 1
0 1 1 0 1 1
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 0 1 1
0 1 1 1 1 1
1 1 1 1 0 0
1 0 0 1 1 0
답: 10
1
4 4
0 0 0 0
1 0 0 0
0 0 1 1
0 1 0 0
답: 4
5
9 10
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
답: 7
3
9 15
0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0
0 0 1 0 1 0 0 0 0
0 1 0 0 1 0 0 0 0
0 1 1 0 0 1 0 0 1
1 0 1 1 1 1 0 0 1
0 1 0 1 0 0 0 0 1
0 1 0 1 0 0 0 0 0
0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 1 1 0
0 0 1 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
답: 16
4. 제출 결과
5. 문제 코드
#include <bits/stdc++.h>
using namespace std;
int memo[222][222][33];
int monkey[222][222];
int horseDir[8][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {2, 1}, {1,2}};
int dir[4][2] = {{1,0}, {0, 1}, {-1, 0}, {0, -1}};
int w,h,k;
int bfs() {
queue<pair<pair<int, int>, int>> q;
q.push({{0,0},0}); memo[0][0][0]=1;
while(!q.empty()) {
int y= q.front().first.first;
int x = q.front().first.second;
int horse = q.front().second;
q.pop();
if (horse + 1 <= k) {
for(int i=0;i<8;i++) {
int dy = y + horseDir[i][0];
int dx = x + horseDir[i][1];
if ( dy < 0 || dx < 0 || dx >= w || dy >= h || monkey[dy][dx] == 1 ) { continue; }
if (memo[dy][dx][horse+1] != 0) { continue; }
memo[dy][dx][horse+1] = memo[y][x][horse] + 1;
q.push({{dy, dx}, horse+1});
}
}
for(int i=0;i<4;i++) {
int dy = y + dir[i][0];
int dx = x + dir[i][1];
if ( dy < 0 || dx < 0 || dx >= w || dy >= h || monkey[dy][dx] == 1) { continue; }
if (memo[dy][dx][horse] != 0) { continue; }
memo[dy][dx][horse] = memo[y][x][horse] + 1;
q.push({{dy, dx}, horse});
}
}
int minTime = 987654321;
for(int i=0; i<=k;i++) {
if(memo[h-1][w-1][i] != 0) {
minTime = min(minTime, memo[h-1][w-1][i]);
}
}
return minTime == 987654321 ? -1 : minTime-1;
}
int main() {
scanf("%d", &k);
scanf("%d %d", &w, &h);
for(int i=0;i<h;i++) {
for(int j=0;j<w;j++) {
scanf("%d", &monkey[i][j]);
}
}
printf("%d", bfs());
}
'Algorithm Problem > 백준' 카테고리의 다른 글
| [백준] 6198번 - 옥상 정원 꾸미기 (0) | 2022.06.21 |
|---|---|
| [백준] 1253번 - 좋다 (0) | 2022.06.20 |
| [백준] 5582번 - 공통 부분 문자열 (0) | 2022.04.02 |
| [백준] 12685번 - 평범한 배낭 (0) | 2022.02.07 |
| [백준] 11052번 - 카드 구매하기 (0) | 2022.01.26 |
