백준 1103번 게임

< 백준 1103번 게임 - 마포 코딩박 >

사용한 알고리즘:  DFS + DP


 Grid 의 칸마다 숫자가 주어지고, 상하좌우로 그 숫자만큼 이동한다. 이때 최대 이동 가능수를 구한다. 처음 시작하는 지점은 왼쪽위(0,0) 지점이다.
처음 시작도 1번으로 카운트 해줘야 한다.
처음 시작을 0번으로 하고, 대신 마지막에 Grid밖으로 움직이는 것을 +1번으로 카운트 해주었다.

문제풀이는 다음과 같다.
(1) (코드: 12~36)
 시작위치 (0,0) 에서 DFS를 사용해 상하좌우로 탐색해주었다.

(2) (코드: dp[50][50])
 dp[i][j] : (i,j) 위치에서 최대 이동가능 횟수 로 저장해주어, 반복적인 탐색을 피해줬다.

(3) (코드: visited[50][50])
 이미 방문했던 위치를 다시 방문할 경우, cycle이 생긴 경우이다. 즉 동전을 무한대로 움직일 수 있는경우이다. 이를 체크해주어 이경우 -1을 출력해주었다.

	#include <bits/stdc++.h>
	using namespace std;
	// 0,0 에서 시작
	int N, M, ans, dp[50][50];
	char arr[50][50];
	// 위 오른쪽 아래 왼쪽
	int dx[4] = {-1,0,1,0};
	int dy[4] = {0,1,0,-1};
	bool visited[50][50];
	bool circle;
	int DFS(int x, int y){
	// Grid 밖
	if(x<0||x>=N||y<0||y>=M) return 0;
	// 홀로 빠짐
	if(arr[x][y]=='H') return 0;
	// cycle 생기면 체크
	if(visited[x][y]){
	circle = true;
	return -1;
	}
	int &ret = dp[x][y];
	// 값을알면 해당 값 출력 (dp)
	if(ret!=-1) return ret;
	visited[x][y] = true;
	// 상하좌우 탐색
	for (int i = 0; i < 4; ++i){
	int nx = x + (arr[x][y]-'0')*dx[i];
	int ny = y + (arr[x][y]-'0')*dy[i];
	// 첫 시작을 0으로 했으니 마지막에 Grid밖으로 움직인것을 대신 카운트 +1번
	ret = max(ret, DFS(nx,ny)+1);
	}
	// 다음으로 빠져나가기 전 지금 본 경로 reset
	visited[x][y] = false;
	return ret;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < M; ++j)
	cin >> arr[i][j];
	memset(dp,-1,sizeof(dp));
	ans = DFS(0,0);
	if(circle) cout << -1 << '\n';
	else cout << ans << '\n';
	return 0;
	}

view raw BOJ 1103.cpp hosted with ❤ by GitHub