문제 이해 단계
https://www.acmicpc.net/problem/1600
원숭이가 두 가지 방법으로 이동하는데
위의 그림처럼 움직이는 것이
일정 횟수만큼 가능하다.
1. 상하좌우 한 칸씩 이동
2. 위 그림처럼 이동 -> 횟수 제한
이 상황일 때 좌측 상단에서 우측 하단까지
가는 최소 움직임(최단 거리)을 구하는 문제
문제 접근 단계
일단 2차원 배열이 주어지고
상하좌우로 움직일 수 있으니 BFS문제라고 생각했다.
거기에다가 특수한 움직임(말의 움직임)이 섞였으니
BFS에 새로운 경로를 추가해서 푸는 문제라고 생각했다.
한 칸씩 이동할 때는
한 번 방문한 위치를 다시 방문하지 않는다.
왜냐하면 방문한 곳을 다시 방문하는 순간
그 경로는 최단 경로라고 할 수 없기 때문이다.
또한 동일한 위치의 방문 횟수는 동일하다.
하지만 해당 문제에서는
똑같은 위치라고 해도 방문 횟수가 달라질 수 있다.
왜냐하면 a라는 위치를 이동할 때
경우의 수가 다양하다.
1. 걸어서 4번 전진
2. 말처럼 두 번씩 전진
3. 말처럼 1번 걸어서 2번 전진
따라서 우리는 방문을 했던 곳도
검사를 해주어 방문 횟수를 기록해야 한다.
해당 문제에서는 말처럼 뛰는 데에는
횟수 제한이 존재하기 때문에
방문을 뜻하는 visit 배열을
횟수에 따라 나눠서 정리했다.
만약 visit [i][j][a]라면 (i, j) 위치는
점프를 a번 사용한 상태라는 뜻이다.
이런 식으로 배열을 통해
각 위치와 점프 횟수별로 배열을 만들어 이동 횟수를 저장해 둔다.
BFS가 진행되는 과정은 다음과 같다.
1. 해당 위치의 점프가 K이하라면 점프 BFS와 상하좌우 BFS 둘 다 돌림
2. 해당 위치의 점프가 K 이상이라면 상하좌우 BFS만 돌림
3. i == H && j == W 면 그때의 이동 횟수를 출력하고 종료
4. 아니라면 -1을 출력하고 종료
문제 구현 단계
int K, W, H;
int map[201][201];
int c[201][201][31];
int hx[] = { -2,-1,1,2,2,1,-1,-2 };
int hy[] = { -1,-2,-2,-1,1,2,2,1 };
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };코드의 선언부이다.
visit을 뜻하는 3차원 배열 c를 선언해 뒀는데,
마지막 배열 부분이 31인 이유는
K의 길이가 문제에서 30이기 때문이다.
밑에 배열 hx와 hy는 말의 움직임을 구현하기 위함이다.
void Bfs(int s1, int s2, int s3) {
queue<tuple<int, int,int>> q;
q.push(make_tuple(s1, s2, s3));
c[s1][s2][s3] = 1;
while (!q.empty()) {
int x = get<0>(q.front());
int y = get<1>(q.front());
int jump = get<2>(q.front());
q.pop();
if (x == H && y == W) {
cout << c[x][y][jump] - 1;
return;
}
if (jump < K) {
for (int i = 0; i < 8; i++) {
int nx = x + hx[i];
int ny = y + hy[i];
if (nx < 1 || nx > H || ny < 1 || ny > W) continue;
if(!c[nx][ny][jump+1] && map[nx][ny] == 0) {
c[nx][ny][jump+1] = c[x][y][jump] + 1;
q.push(make_tuple(nx, ny, jump + 1));
}
}
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > H || ny < 1 || ny > W) continue;
if (!c[nx][ny][jump] && map[nx][ny] == 0)
{
c[nx][ny][jump] = c[x][y][jump] + 1;
q.push(make_tuple(nx, ny, jump));
}
}
}
cout << "-1";
return;
}핵심 BFS 함수이다.
매개변수로 x, y, jump 값을 넘기고 받기 위해 tuple을 사용했다.
이 세 가지 값을 큐에 넣은 다음 visit 값을 올려준다.
여기 시 visit 값을 이용하여 이동 횟수를 체크했다.
jump < K 일 때는 말의 움직임을 구현하는데,
여기서 중요한 것은 jump 하는 visit배열이 이미 방문했는지
확인하는 것과 그 값에 +1을 해주는 것이 중요하다.
그 작업이 끝나면 상하좌우 한 칸씩 이동하는 작업은
항상 일어나기 때문에 상하좌우를 이동해 준다.
이때는 jump가 일어나지 않으므로
큐에 넣어줄 때 jump값은 그대로 둔다.
이 작업을 큐가 빌 때까지 ( 이때는 실패했으므로 -1 )
혹은 x == H && x == W(이때 이동 횟수 출력) 일 때까지 반복한다.
이 문제의 핵심은 여기기 때문에
마지막으로 전체 코드를 올리고 마무리하겠다.
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int K, W, H;
int map[201][201];
int c[201][201][31];
int hx[] = { -2,-1,1,2,2,1,-1,-2 };
int hy[] = { -1,-2,-2,-1,1,2,2,1 };
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
void Bfs(int s1, int s2, int s3) {
queue<tuple<int, int,int>> q;
q.push(make_tuple(s1, s2, s3));
c[s1][s2][s3] = 1;
while (!q.empty()) {
int x = get<0>(q.front());
int y = get<1>(q.front());
int jump = get<2>(q.front());
q.pop();
if (x == H && y == W) {
cout << c[x][y][jump] - 1;
return;
}
if (jump < K) {
for (int i = 0; i < 8; i++) {
int nx = x + hx[i];
int ny = y + hy[i];
if (nx < 1 || nx > H || ny < 1 || ny > W) continue;
if(!c[nx][ny][jump+1] && map[nx][ny] == 0) {
c[nx][ny][jump+1] = c[x][y][jump] + 1;
q.push(make_tuple(nx, ny, jump + 1));
}
}
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > H || ny < 1 || ny > W) continue;
if (!c[nx][ny][jump] && map[nx][ny] == 0)
{
c[nx][ny][jump] = c[x][y][jump] + 1;
q.push(make_tuple(nx, ny, jump));
}
}
}
cout << "-1";
return;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> K >> W >> H;
for (int i = 1; i <= H; i++)
for (int j = 1; j <= W; j++) cin >> map[i][j];
Bfs(1, 1, 0);
}
시행착오
푸는데 실패했던 문제.
굉장히 시간이 오래 걸렸던 문제이다.
내 생각에는 아무리 해봐도 맞는 거 같은데,
자꾸만 틀리게 나와서 애먹었다.
처음에는 점프하는 게 당연히 더 빠를 줄 알고
우선순위 큐나 덱을 써서 문제를 풀었는데 계속 틀렸다.
아무리 고민해 봐도 안 나오길래 인터넷을 참고했는데
3차원 배열을 쓰는 신박한 방법이 있는지 몰랐다.
역시 나는 아직 멀었다.
BFS는 자신 있다고 생각했는데
아직 한참 먼 거 같다.
좀 더 다양한 케이스를 공부해 보고
문제를 더 많이 풀어봐야겠다.