백준 1890 - 점프 (C++)
문제는 이러하다.
각 칸에는 가중치가 입력되어 있으며, 해당 발판에서는 가중치만큼 오른쪽 혹은 아래로 이동할 수 있다.
규칙대로 이동하여 도착지점(우측 하단)에 도착할 수 있는 경우의 수를 구하면 된다.
문제 풀이
본인은 DFS와 DP를 사용하여 풀었다.
DFS, DP에 대해 모른다면, 찾아보고 오는 것을 추천한다.
먼저 예제 입력을 보자.
입력에 대한 맵과 동일한 크기의 DP배열을 만들어 놓았다.
좌측이 입력받은 배열이며, 우측이 DP배열이다.
먼저 한 가지 방향으로 먼저 쭉 진행해보자.
이런 방향으로 이동할 수 있을 것이다.
도착 했으니, DP배열의 도착지점의 값을 1로 바꿔주겠다.
도착했으니, 뒤로 돌아오며 다음 길을 탐색해야 한다.
돌아오면서, 다음 위치의 DP배열 값을 이전 위치에 더해줄 것이다.
예를 들어, (1,1)에서 (0,0)으로 돌아갈 때, DP배열의 (1,1) 값이 2였다면, DP배열의 (0,0) 값에 2를 더해줄 것이다.
DP배열의 값은 해당 좌표로부터 도착 지점(우측 하단)까지 탐색된 경로의 수를 의미한다.
이렇게 말이다.
그럼, 다음 길을 다시 찾아보자.
이런 경로도 있을 것이다.
근데, 마지막 빨간색 화살표는 보면 도착 지점의 DP배열의 값이 0이 아니다.
즉 이미 그 이후의 길을 탐색한 적이 있다는 것이며, 다시 탐색할 이유는 없다는 것이다.
그대로 다시 뒤로 돌아가며 다음 길을 탐색하자.
물론 돌아가면서 DP의 값도 갱신해줄 것이다.
여기까지 갱신하며 돌아왔다면, 다음 길을 찾을 수 있다.
이렇게 다음 길을 진행할 수 있다.
빨간색 화살표를 보면, 위에서 말했듯이 굳이 탐색할 필요가 없다.
그대로 돌아오며 DP를 갱신해주자.
돌아오며, 값을 더해주며 돌아오면? 오른쪽처럼 (0,0)의 값이 3이 되어있다.
답은 3이다. 그대로, Dp배열의 (0,0) 값을 출력해주면 된다.
풀이 코드
int Width = 0;
std::vector<std::vector<int>> Board;
std::vector<std::vector<long long>> DP;
먼저, 입력을 저장할 Width, Board를 선언하고
DP배열까지 선언해주자.
std::cin >> Width;
Board.resize(Width, std::vector<int>(Width, 0));
DP.resize(Width, std::vector<long long>(Width, 0));
for (int i = 0; i < Width; i++)
{
for (int j = 0; j < Width; j++)
{
std::cin >> Board[i][j];
}
}
이후, resize 해준 뒤에 입력을 저장해주면 된다.
DFS(0, 0);
std::cout << DP[0][0];
return 0;
그 이후엔, 이렇게 간단하게 DFS함수 하나만 호출해주고 (0, 0)의 값을 출력해주면 된다.
아래는 DFS함수의 코드 전문이다.
long long DFS(int _X, int _Y)
{
if (_X == Width - 1 && _Y == Width - 1)
{
return 1;
}
if (Board[_Y][_X] == 0)
{
return 0;
}
if (DP[_Y][_X] != 0)
{
return DP[_Y][_X];
}
int CurWeight = Board[_Y][_X];
{
int NextRightX = _X + CurWeight;
int NextRightY = _Y;
if (NextRightX < Width && NextRightY < Width)
{
DP[_Y][_X] += DFS(NextRightX, NextRightY);
}
}
{
int NextDownX = _X;
int NextDownY = _Y + CurWeight;
if (NextDownX < Width && NextDownY < Width)
{
DP[_Y][_X] += DFS(NextDownX, NextDownY);
}
}
return DP[_Y][_X];
}
우측과 좌측을 탐색하며, 재귀적으로 함수를 호출한다.
먼저, 가장 위의 조건문을 보면 도착지점에 도착했다면 DP배열의 값을 1로 바꾼 뒤, 함수를 return한다.
두 번째 조건이 중요하다. 본인은 저 조건문을 추가하지 않아서 메모리 초과가 뜬 경우가 있었다.
가중치가 0이라면, 오른쪽이든 아래쪽이든 이동하지 못하고 무한 루프를 돌기 때문에, 반드시 예외처리를 해주어야 한다.
세번째 조건문은 현재 위치로부터 도착지점까지 이미 탐색한 경로가 있다면, 굳이 한 번 더 탐색하지 않기 위한 조건문이다. 위에서 설명했듯이 DP배열의 값은 해당 위치로부터 도착ㄹ지점까지 이어진 경로의 수를 의미하며, 이미 탐색한 적이 있다면 굳이 한 번 더 탐색할 이유는 없다.
이 3가지 조건문을 뚫고 아래까지 도달했다면, 이제 우측과 아래쪽에 대해 탐색을 진행하면 된다.
이 문제에서 주의해야 할 점은 두가지이다.
1. 가중치가 0일 때 예외처리를 해주어야 한다.
2. DP 배열의 값은 int가 아니라 long long으로 저장해야 한다.
DFS를 알고 있다면, 크게 어려운 문제는 아니지만 처음 접하면 다소 헷갈릴 수 있는 문제이다.
이런 문제는 필자처럼 직접 경우의 수를 그려보며 생각하면 이해가 쉽게 될 것이다.
