[백준] 1103 게임

DP + 그래프 사이클 체크를 통해 풀 수 있는 문제다!

 

처음에 dp가 생각났지만 굳이 dp를 써야하나?

라는 생각으로 실패의 길로 빠져들어갔다

 

먼저 bfs+set을 통해 차근차근 넣어주고 지나간 정점은 set으로 확인해서 실패~

=> 1->2를 갈 때와 3->2를 갈때 둘다 2에가서 사이클로 체크됨 ㅠㅠ

 

그리고 착하게 dfs로 그래프 그려가고 방문한점을 다시 방문하면 사이클 확인은 시간초과~

=> 정점 n*m개에서 4개의 행동을 할 수 있어서 4^n*m인 것 같다!

 

결국 여기서 dp로 d[x][y] (x,y)에서 갈 수 있는 최대 수 를 찾아가며 cycle을 동시에 찾으면 된다!

 

dp를 짜는건 기본 dp문제와 똑같이 짜면 된다! 예외는 없다 범위를 넘어가거나 H라면 안가고

그게 아니라면 +1하며 다음칸을 찾아가면 된다

 

여기서 cycle을 확인해야하는데 확인하는 방법은 내가 방문한점을 true로 체크해주고

그 상태로 다음정점으로 넘어가고 계속 dfs로 타고들어가다가 만약 현재 방문한점이 true면 

처음 방문했을 때 끝나지 않고 다시 나의 위치로 돌아왔다는 것이므로 cycle이 된다!

 

dfs가 끝날 때 체크를 false로 바꿔주면 이런 방식으로 cycle을 확인 할 수 있다!

 

풀고나니 기본 dp문제에 + cycle 체크만 한건데 어려웠다..!

시간복잡도 계산 잘해야하는데 어렵다..!

 

쉬운길보다 최적화된 방법을 찾는 연습을해야한다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m;
int d[55][55];
bool visited[55][55];
int dx[4] = {0,0,-1,1}; 
int dy[4] = {1,-1,0,0};
char map[55][55];
 
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<m);
}
 
int solve(int x,int y) {
    if(visited[x][y]) return 1e9;
    int&ret = d[x][y];
    if(ret != -1) return ret;
    ret=0;
    
    visited[x][y]= 1;
    int c = map[x][y]-'0';
    for(int i=0;i<4;i++){
        int nx = x+dx[i]*c;
        int ny = y+dy[i]*c;
        if(inner(nx,ny) && map[nx][ny] != 'H') {
            ret = max(ret,solve(nx,ny)+1);
        }
    }
    visited[x][y]=0;
    return ret;
}
 
int main(){
    memset(d,-1,sizeof(d));
    scanf(" %d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %1c",&map[i][j]);
        }
    }
    int ans = solve(0,0);
    printf("%d\n",(ans>=1e9) ? -1 : ans+1);
}