Gidhub BE Developer

[BOJ] 게임

2018-02-01
goodGid
Algorithm

Problem

Problem URL : 게임

Code


#include <iostream>
using namespace std;
int dx[5] = { 0,0,-1,1 };
int dy[5] = { 1,-1,0,0 };
int map[51][51];
int d[51][51]; // d is DP
bool v[51][51]; // v is Visit
int n,m,ans;

void dfs(int x,int y,int idg){
    if(v[x][y]) {
        cout << "-1" << endl;
        exit(0);
    }
    v[x][y] = true;
    d[x][y] = idg;
    ans = ans < idg ? idg : ans;
    
    for(int i=0; i<4; i++){
        int nx = x + dx[i] * map[x][y];
        int ny = y + dy[i] * map[x][y];
        
        if(nx > 0 && nx <=n && ny > 0 && ny <= m && map[nx][ny] != -1 && d[nx][ny] <= idg)
            dfs(nx,ny,idg+1);
    }
    v[x][y] = false;
}

int main(){
    cin >> n >> m;
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            char c;
            cin >> c;
            if( c == 'H') map[i][j] = -1;
            else map[i][j] = c - '0' ;
        }
    
    dfs(1,1,1);
    cout << ans << endl;
    return 0;
}

Feed Back

if(v[x][y]) {
        cout << "-1" << endl;
        exit(0);
    }

  • exit(0)을 해주면 프로그램이 종료가 된다.

  • 이전에는 main에서 호출한 함수에서 return ;을 해주고 main에서 종료를 해줬는데
    exit(0)을 사용하면 Code가 간결해진다.

Anser Condition Code

if(nx > 0 && nx <=n && ny > 0 && ny <= m && map[nx][ny] != -1 && d[nx][ny] <= idg)
            dfs(nx,ny,idg+1);

Wrong Condition Code

if(nx > 0 && nx <=n && ny > 0 && ny <= m && map[nx][ny] != -1)
            dfs(nx,ny,idg+1);

  • d[nx][ny] <= idg 조건의 유무에 따라 Anser or Wrong

  • 저 이유 찾는게 너무 어려웠다. ㅡ.ㅡ^

  • 이제 (x,y)를 가려고 할 때 그 전에 (x,y)값이 존재한다면 그 뜻은 다른 경로로 (x,y)를 visit했다는 뜻이다.
    그래서 만약에 현재 내가 가는 경로에서 다음에 탐색할 위치가 (x,y)일 때 그 값이 내가 지금 갖고있는 idg값보다 클 경우에는 (x,y)를 갈 필요가 없기 때문에 조건을 추가해주어야지 시간 초과가 안나게 된다.

Index