- 3차원 배열 bfs문제였다.
- 처음엔 2차원 배열로 했다가 틀렸다. 3차원으로 해야 하는 이유는 말을 통해서 가는 거리와 원숭이가 가는 거리를 분리해줘야 하기 때문이다.
말을 이용해서는 목적지까지 도착을 못한다고 가정해보자. (원숭이만을 이용해서 갈 수 있다고 가정) 2차원 배열에 path를 등록하여 이미 지나간 거리를 지나가지 않는다면 도착지까지 도달하지 못할 것이다. 그래서 말을 사용했을 때 path를 분리해주어야 한다.
반례:
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이 나왔다.
정답:
#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX 201
using namespace std;
int k, w, h;
int monkey[MAX][MAX];
int path[30][MAX][MAX];
struct Move
{
int x, y, horse;
};
int kx[8] = {2, 1, 2, 1, -2, -1, -2, -1};
int ky[8] = {1, 2, -1, -2, 1, 2, -1, -2};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool isValid(int row, int col)
{
if (row < 0 || col < 0 || row > h - 1 || col > w - 1)
{
return false;
}
return true;
}
int main(void)
{
scanf("%d%d%d", &k, &w, &h);
queue<Move> q;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
scanf("%d", &monkey[i][j]);
}
}
q.push({0, 0, k});
memset(path, 0, sizeof(path));
while (!q.empty())
{
Move fr = q.front();
q.pop();
if (fr.x == w - 1 && fr.y == h - 1)
{
printf("%d\n", path[fr.horse][fr.y][fr.x]);
return 0;
}
if (fr.horse > 0)
{
for (int i = 0; i < 8; i++)
{
int nX = fr.x + kx[i];
int nY = fr.y + ky[i];
if (isValid(nY, nX) && !monkey[nY][nX] && !path[fr.horse - 1][nY][nX])
{
path[fr.horse - 1][nY][nX] = path[fr.horse][fr.y][fr.x] + 1;
q.push({nX, nY, fr.horse - 1});
}
}
}
for (int i = 0; i < 4; i++)
{
int nX = fr.x + dx[i];
int nY = fr.y + dy[i];
if (isValid(nY, nX) && !monkey[nY][nX] && !path[fr.horse][nY][nX])
{
path[fr.horse][nY][nX] = path[fr.horse][fr.y][fr.x] + 1;
q.push({nX, nY, fr.horse});
}
}
}
printf("-1\n");
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 13913] 숨바꼭질 4 (0) | 2020.11.01 |
---|---|
[백준 13549] 숨바꼭질3 (0) | 2020.10.29 |
[백준 6593] 상범빌딩 (0) | 2020.10.28 |
[백준 7569] 토마토 (0) | 2020.10.27 |
[백준 11725] 트리의 부모 찾기 (0) | 2020.10.04 |
댓글