백준 1103 게임

문제 설명

• 1부터 9까지 쓰여진 보드
• 왼쪽 위부터 출발
• 왼 오 위 아래 중 한 방향으로 쓰여있는 만큼 이동
• 구멍에 빠지거나 바깥으로 나가면 게임오버

최대 동전을 움직일 수 있는 수를 구하는 문제 (무한번이면 -1)

해결

dfs를 이용한 탐색으로 해결

void dfs(int x,int y,int cnt)

• x,y : 현재 위치한 좌표
• cnt : 이동한 횟수

char map[51][51];
int visit[51][51];
int dp[51][51];

• map : 문제 입력 보드 수
• visit : 방문 여부
• dp : dp 이용한 수 저장 (후에 설명)

dfs

	if(visit[x][y]==1){
		Max = 999999;
		return;
	}
	

1. 현재 위치의 visit가 1임
   같은 칸으로 돌아왔다는 뜻은 순환이 가능하다는 뜻
   따라서 무한 반복 가능하다는 뜻이다
   -> Max를 최대로 바꾸고 함수 종료

	visit[x][y] = 1;

2. visit를 1로 바꾸어서 방문여부 표기

	for(int i=0;i<4;i++){
		int xx = x + _x[i]*(map[x][y]-'0');
		int yy = y + _y[i]*(map[x][y]-'0');
		if(xx>=0&&yy>=0&&xx<m&&yy<n&&map[xx][yy]!='H'){ // 이동 가능할때  
			dfs(xx,yy,cnt+1);
		}else{ // 빠질때  
			if(Max == 999999)
				return;
			
			if(Max<cnt+1){
				Max = cnt+1;
			}
		}
	}

3. for문을 통해 상하좌우 이동

int xx = x + _x[i]*(map[x][y]-'0');
int yy = y + _y[i]*(map[x][y]-'0');

map[xx][yy] : 미래 이동할 위치

• 이동 가능하다면 : dfs(xx,yy,cnt+1) 로 이동한 이후의 Max 재귀적으로 구함

• 이동 불가능하다면 : 종료하는 것이 아니라 구멍에 빠지는 이동횟수도 계산에 포함하므로 cnt+1로 이동횟수를 가정한 다음 Max를 이에 맞게 변경

	visit[x][y] = 0;

4. visit를 0으로 변경

visit는 한 경로에 대해서 무한루프를 도는 건지 확인하는 용도

첫번째 중복 방문 그림은 무한루프를 도는것이 맞지만
두번째 중복 방문은 무한루프를 도는 것이 아니다

따라서 visit는 한 경로에 대해서만 표기해야함..

시간초과 해결

위의 경우만 고려하면 시간초과가 나게 된다...

dp까지 이용해서 한번 더 계산을 걸러주어야 함

if(dp[x][y]>=cnt){
		return;
}
dp[x][y]=cnt;

dp 배열에다 방문시 제일 큰 cnt를 저장해둔다

-> 다른 재귀 반복때 같은 칸 방문시 dp에 저장된 수보다 cnt가 작다면 굳이 뒤를 계산할 필요가 없게 된다 (어짜피 dp가 큰 방문때의 cnt보다 작은 값이 나오게 됨)

코드

#include <stdio.h>
#include <string.h>

char map[51][51];
int visit[51][51];
int dp[51][51];
int Max = 0;
int _x[4] = {0,0,1,-1};
int _y[4] = {1,-1, 0,0};
int m,n;

void dfs(int x,int y,int cnt){
	if(visit[x][y]==1){
		Max = 999999;
		return;
	}
	if(dp[x][y]>=cnt){
		return;
	}
	dp[x][y]=cnt;
	visit[x][y] = 1;
	
	for(int i=0;i<4;i++){
		int xx = x + _x[i]*(map[x][y]-'0');
		int yy = y + _y[i]*(map[x][y]-'0');
		if(xx>=0&&yy>=0&&xx<m&&yy<n&&map[xx][yy]!='H'){ // 이동 가능할때  
			dfs(xx,yy,cnt+1);
		}else{ // 빠질때  
			if(Max == 999999)
				return;
			
			if(Max<cnt+1){
				Max = cnt+1;
			}
		}
	}
	visit[x][y]=0;
	
}

int main(){
	memset(dp, -1, sizeof(dp));
	
	scanf("%d %d",&m,&n);
	for(int i=0;i<m;i++){	
		scanf("%s",&map[i]);
		
	}
	dfs(0,0,0);
	if(Max == 999999)
		printf("-1");
	else
		printf("%d",Max);
	
}