백준 알고리즘 풀이 1890번 - 점프

https://www.acmicpc.net/problem/1890

1890번: 점프

---

백준 1890번

- 백트래킹을 이용한 dp문제.

 

알고리즘

---

1.  dp배열에 마지막 칸을 1로, 나머지는 0으로 초기화한다. 

2. 백트래킹을 활용한 dfs를 사용해서, 방문한적이 있는 노드를 방문한다면, dp[nowY][nowX]+=dp[nextY][nextX]

방문하지 않은 노드라면, 그 지점에서 dfs를 돌려준다.

3. 결국 처음 값 dp[1][1]이 정답으로 도출됨을 알 수 있다.

시간 복잡도

---

처음에는 그냥 일반적인 dfs를 사용해서 문제를 풀어보았다.

<틀린 소스 코드>

#include <iostream>
//weird code
using namespace std;

int map[101][101];
long long int dp[101][101]={0,};
long long int dim;
int count=0;

void jump(int x,int y,int block)
{
	count++;
	if(x>dim || y>dim) return;
	if(x==dim && y==dim) return;
	int kanX=x+block, kanY=y+block;
	
	cout<<"y : "<<y<<" x : "<<x<<endl;
	
	if(kanX<=dim){
		dp[y][kanX]+=dp[y][x];
		jump(kanX,y,map[y][kanX]);
	}	
	if(kanY<=dim){
		dp[kanY][x]+=dp[y][x];
		jump(x,kanY,map[kanY][x]);
	}	
	//중복처리를 안함
}

int main() 
{
	cin>>dim;
	for(int i=1;i<=dim;i++){
		for(int j=1;j<=dim;j++){
			scanf("%lld",&map[i][j]);
		}
	}
	dp[1][1]=1;
	
	
	jump(1,1,map[1][1]);
	for(int i=1;i<=dim;i++){
		for(int j=1;j<=dim;j++){
			cout<<dp[i][j];
		}
		cout<<endl;
	}
	cout<<"count 입니다 "<<count<<endl;
	cout<<dp[dim][dim];
}

 

계속 시간 초과가 나와서, 방문하는 값들을 찾아보니 반복적으로 방문하고 있었다.

그래서 백트래킹을 이용해서 dp를 돌리기로 하였다.

 

시간 복잡도

---

map을 입력받는데 O(N) = N^2. 최악의 경우 map에 모든 값이 1인 경우.

점화식 f(n) = f(n-1) + f(n-1), f(0) = 1

 

예외 조건

---

map의 값이 0인 경우가 있다. 이때 메모리 초과가 나는데 이 경우를 따로 빼서 처리해야한다. 

 

소스코드

---

#include <iostream>

using namespace std;

int map[101][101];
long int dp[101][101]={0,};
long int dim;

void jump(int x,int y)
{
	int move[2][2]={{map[y][x],0},{0,map[y][x]}};
	if(x>dim || y>dim) return;
	for(int i=0;i<=1;i++){
		long int nextX=move[i][0]+x,nextY=move[i][1]+y;
		if(nextX==x && nextY==y) break;
		if(dp[nextY][nextX]==0){
			jump(nextX,nextY);
		}//방문한적 없다면
		dp[y][x]+=dp[nextY][nextX];		
		//방문 했었다면	
	}
}

int main() 
{
	scanf("%d",&dim);
	for(int i=1;i<=dim;i++){
		for(int j=1;j<=dim;j++){
			scanf("%lld",&map[i][j]);
		}
	}
	dp[dim][dim]=1;
	jump(1,1);
	printf("%ld",dp[1][1]);
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)