BOJ 1600 - 말이 되고픈 원숭이
“3차원 배열 BFS”
BOJ 1600 - 말이 되고픈 원숭이
문제 링크
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
int K, W, H;
int board[220][220];
int dist[220][220][31];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dhx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dhy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>K>>H>>W;
for (int i = 0; i < W; i++) {
for (int j = 0; j < H; j++)
cin >> board[i][j];
}
int hp = K; // Horse Point kk
for (int i = 0; i < W; i++)
for (int j = 0; j < H; j++)
for (int k = 0; k <= K; k++)
dist[i][j][k] = -1;
queue<tuple<int,int,int>> q;
q.push({0,0,hp});
dist[0][0][hp] = 0;
while (!q.empty())
{
auto cur = q.front(); q.pop();
int cx = get<0>(cur); int cy = get<1>(cur);
int ch = get<2>(cur);
if (cx == W-1 && cy == H-1) {
cout << dist[cx][cy][ch]; return 0;
}
for (int dir = 0; dir < 4; dir++) {
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= W || ny < 0 || ny >= H)
continue;
if (dist[nx][ny][ch] != -1 || board[nx][ny])
continue;
dist[nx][ny][ch] = dist[cx][cy][ch] + 1;
q.push({nx,ny,ch});
}
if (ch > 0) {
for (int dir = 0; dir < 8; dir++) {
int nx = cx + dhx[dir];
int ny = cy + dhy[dir];
if (nx < 0 || nx >= W || ny < 0 || ny >= H)
continue;
if (dist[nx][ny][ch - 1] != -1 || board[nx][ny])
continue;
dist[nx][ny][ch - 1] = dist[cx][cy][ch] + 1;
q.push({nx,ny,ch-1});
}
}
}
cout << -1;
return 0;
}
BFS 문제가 난이도가 점점 올라가면서, 단순히 BFS만 도는게 아니라 생각할 게 많아지기 시작하는데 여러 문제들을 풀면서 감각이 조금 생겼다고 생각한 순간 나타나서 그게 아니었다는 것을 처절하게 알려준 문제.
원숭이는
(0, 0)에서(H-1, W-1)까지 움직이는데, 그 동안 K회 체스판의 말처럼 움직일 수가 있다. 내가 첫번째로 떠올린건 백트래킹을 이용한 풀이였다. 바킹독 BFS 문제집에서 뽑고 들어간거긴 했는데 일단 백트래킹으로 풀어보았었다. 아래와 같이solve()를 재귀로 돌면서 모든 경우의 수를 체크했다.
#include <bits/stdc++.h>
const int INF = 0x3f3f3f3f;
using namespace std;
int K, W, H;
int board[220][220];
int dist[220][220];
int vis[220][220];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dhx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dhy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool d = false;
vector<pair<int,int>> sp;
void solve(int x, int y, int hp)
{
if (d) return ;
if (x == W - 1 && y == H - 1) {
d = true; return;
}
if (x < 0 || x >= W || y < 0 || y >= H)
return ;
if (hp > 0) {
for (int dir = 0; dir < 8; dir++) {
int nx = x + dhx[dir];
int ny = y + dhy[dir];
if (nx < 0 || nx >= W || ny < 0 || ny >= H)
continue ;
if (board[nx][ny])
continue;
dist[nx][ny] = dist[x][y] + 1;
solve(nx, ny, hp - 1);
if (d) return ;
dist[nx][ny] = -1;
}
}
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || nx >= W || ny < 0 || ny >= H)
continue ;
if (dist[nx][ny] != -1 || board[nx][ny])
continue;
dist[nx][ny] = dist[x][y] + 1;
solve(nx, ny, hp);
if (d) return ;
dist[nx][ny] = -1;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>K>>H>>W;
for (int i = 0; i < W; i++) {
for (int j = 0; j < H; j++)
cin >> board[i][j];
}
int hp = K; // Horse Point kk
for (int i = 0; i < W; i++)
fill(dist[i], dist[i] + H, -1);
dist[0][0] = 0;
solve(0, 0, hp);
if (d)
cout << dist[W - 1][H - 1];
else
cout << -1;
return 0;
}
- 결과적으로 보자면 이 코드는 시간 초과가 발생한다. 재귀를 돌면서 모든 수를 보기 때문이었던 걸로 보인다. 이동 횟수를 말 이동에도 저장하고, 그냥 이동에도 저장하면서 보드에 혼선이 생기게 된다. 이 결국 이 문제는 BFS로 풀어야 하는게 맞다. 또 말 이동 횟수라는 또 다른 정보를 기록하기 위해 dist를 삼중 배열로 사용해야 한다. 이런 식으로 일차원 배열을 이차원 배열로 늘리고, 이차원 배열을 삼차원으로 늘리는 생각을 뚫기가 참 어려운 것 같다… 그렇게 작성한 코드는 아래와 같다.
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
int K, W, H;
int board[220][220];
int dist[220][220][31];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dhx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dhy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>K>>H>>W;
for (int i = 0; i < W; i++) {
for (int j = 0; j < H; j++)
cin >> board[i][j];
}
int hp = K; // Horse Point kk
for (int i = 0; i < W; i++)
for (int j = 0; j < H; j++)
for (int k = 0; k <= K; k++)
dist[i][j][k] = -1;
queue<tuple<int,int,int>> q;
q.push({0,0,hp});
dist[0][0][hp] = 0;
while (!q.empty())
{
auto cur = q.front(); q.pop();
int cx = get<0>(cur); int cy = get<1>(cur);
int ch = get<2>(cur);
if (cx == W-1 && cy == H-1) {
cout << dist[cx][cy][ch]; return 0;
}
for (int dir = 0; dir < 4; dir++) {
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || nx >= W || ny < 0 || ny >= H)
continue;
if (dist[nx][ny][ch] != -1 || board[nx][ny])
continue;
dist[nx][ny][ch] = dist[cx][cy][ch] + 1;
q.push({nx,ny,ch});
}
if (ch > 0) {
for (int dir = 0; dir < 8; dir++) {
int nx = cx + dhx[dir];
int ny = cy + dhy[dir];
if (nx < 0 || nx >= W || ny < 0 || ny >= H)
continue;
if (dist[nx][ny][ch] != -1 || board[nx][ny])
continue;
dist[nx][ny][ch - 1] = dist[cx][cy][ch] + 1;
q.push({nx,ny,ch-1});
}
}
}
cout << -1;
return 0;
}
- 정답 코드랑 뭐가 다른가 싶지만, 이 코드를 제출하면 메모리 초과가 발생한다. 사실 시간 초과와 다르게 메모리 초과는 정확한 메모리 계산이 어려워서 꽤 난감한 부분인데, 오랜 시간 해답을 찾아다닌 끝에, 말 이동 상황 시 중복 체크를 할 때 말 이동을 하면서 nx, ny에 온 적이 있는지를 체크하지 않았다는 것이 문제라는 것을 확인했다. 그러니까…
if (ch > 0) {
for (int dir = 0; dir < 8; dir++) {
int nx = cx + dhx[dir];
int ny = cy + dhy[dir];
if (nx < 0 || nx >= W || ny < 0 || ny >= H)
continue;
// 아래 if 문이 문제
// if (dist[nx][ny][ch - 1] != -1 || board[nx][ny]) 로 수정해야 함
if (dist[nx][ny][ch] != -1 || board[nx][ny])
continue;
dist[nx][ny][ch - 1] = dist[cx][cy][ch] + 1;
q.push({nx,ny,ch-1});
}
}
}
if (dist[nx][ny][ch] != -1 || board[nx][ny])에서,dist[nx][ny][ch]는 말 좌표 이동을 하고도 말 이동 횟수가 깎이지 않는 지점의 value인데,(nx, ny)는 이동한 이후의 좌표이기 때문에 말 이동을 했다는 가정 하에 ch도 1을 깎은 지점을 확인해줘야 한다는 거다. 그 다음dist[nx][ny][ch - 1] = dist[cx][cy][ch] + 1;로dist[nx][ny][ch - 1]를 갱신하는 게 옳다. ch - 1를 확인하지 않고 ch를 확인하느라 queue가 계속 헛돌아서 메모리 초과가 발생했던 것으로 보인다. 하루종일 헤맨 것 치고는 허무한 결말이 아닐 수가 없다…
