[백준알고리즘] 1890번: 점프 -C++

[백준알고리즘] 1890번: 점프 -C++

1890번: 점프 (acmicpc.net)

1890번: 점프

누가 봐도 동적 계획법으로 풀어야 할 것 같은 문제다. 그래서 가능한 모든 경우를 찾는데 재귀를 사용했고, DFS를 사용했다.

 

사실 이전에 Python으로 풀었던 문제였다. 물론 기억은 나질 않았지만.. 아래 링크가 이전에 풀었던 코드다.

[백준알고리즘] 1890번: 점프 -Python (tistory.com)

[백준알고리즘] 1890번: 점프 -Python

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

우선 풀이 방법에 대해서 설명하도록 하겠다.

 

시작 위치는 가장 위의 왼쪽 끝 지점이며, 도착 위치는 가장 아래의 오른쪽 끝 지점이다.

 

시작 위치에서 도착 위치로 이동할 때에는 각 지점에 지정한 값만큼 점프를 해야 한다. 점프의 방향은 오른쪽과 아래쪽이다. 점프의 방향이 두 방향밖에 주어지지 않아서 굉장히 쉽게 풀 수 있다.

 

다만, 재귀로 풀 때 주의해야할 점이 있다.

 

먼저, 도착 위치에 도착한 경우를 처리해주는 것과 \( N \times N \) 게임판의 범위 밖으로 점프해버리는 것을 처리하는 것은 기본이다. 또한, 가능한 경로의 개수가 \( 2^{63} - 1 \)이기 때문에 int만 이용하면 오버플로우가 발생할 수 있다.

 

추가적으로 하나 더 주의해야 하는데, 점프 값이 0으로 주어진 칸에 도착한 경우에는 재귀를 시도하면서 무한루프에 빠지지 않게 해주는 것이다. 0인 칸에 도착해서 처리를 해주지 않고 그저 다른 경우와 같이 재귀 함수를 호출해온다면, 해당 칸에서 벗어나지 못하고 계속 제자리 점프만 할 것이다.

이 부분만 해결해준다면, 문제는 쉽게 풀 수 있다.

 

재귀를 돌아오면서 가능한 각 칸의 가능한 경로의 수를 return해주면 된다.

 

---

 

아래는 위의 방식대로 구현한 C++ 코드다.

 

이번 코드... 뭔가 길어보이지만, 사실 그렇게 어렵게 짠 것은 아니다. 인자로 \( x \), \( y \)를 계속 넘기는 것 대신 POSITION이라는 객체를 하나 만들어서 처리해준 것이 전부다. 이렇게 객체를 만들어 처리해줌으로써 dfs 함수 안에서 두 위치를 비교하는 코드가 상대적으로 깔끔해진다고 느꼈기 때문에 추가해줬다.

 

생성자를 굳이 overloading 해줄 필요는 없었을 것 같다. 비교를 위해서 operator==를 overriding 해주었다.

#include <iostream>
#include <vector>

struct POSITION
{
	int x, y;

	POSITION() {};
	POSITION(int x, int y)
		:x(x), y(y)
	{}

	bool operator == (const POSITION& target)
	{
		return (this->x == target.x && this->y == target.y);
	}
};

void solve(void);

int main(int argc, char** argv)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int64_t dfs(std::vector<std::vector<int>>& map, std::vector<std::vector<int64_t>>& visit, 
			POSITION currPosition)
{
	int length = map.size() - 1;
	if (currPosition == POSITION(length, length))
		return 1;

	if (0 <= visit[currPosition.y][currPosition.x])
		return visit[currPosition.y][currPosition.x];

	const int& jump = map[currPosition.y][currPosition.x];

	if (0 == jump)
	{
		visit[currPosition.y][currPosition.x] = 0;
		return 0;
	}

	int64_t pathCount = 0;

	if (currPosition.x + jump <= length)
		pathCount += dfs(map, visit, POSITION(currPosition.x + jump, currPosition.y));

	if (currPosition.y + jump <= length)
		pathCount += dfs(map, visit, POSITION(currPosition.x, currPosition.y + jump));

	visit[currPosition.y][currPosition.x] = pathCount;

	return pathCount;
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<std::vector<int>> jumpMap(n, std::vector<int>(n));
	std::vector<std::vector<int64_t>> visited(n, std::vector<int64_t>(n, -1));


	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			std::cin >> jumpMap[i][j];

	std::cout << dfs(jumpMap, visited, POSITION(0, 0));
}