[C++] 게임

백준 1103번 게임 문제!

 

문제

 

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

 

입력

 

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

 

출력

 

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

 

코드

 

#include <stdio.h>
#include <stdlib.h>
#define MIN(a,b) (((a)<(b))?(a):(b))
 
char graph[55][55];
int dp[55][55];
int visit[55][55];
 
int dx[4] = {-1,0,0,1};
int dy[4] = {0,1,-1,0};
 
int N,M;
int ans = -1;
 
void dfs(int x,int y,int cnt){
    if(ans<cnt) ans = cnt;
    int mul = graph[x][y]-'0';
    for(int i = 0 ; i < 4 ; i++){
        int next_x = x+dx[i]*mul;
        int next_y = y+dy[i]*mul;
        if(next_x>=0 && next_y >=0 && next_x < N && next_y < M){
            if(graph[next_x][next_y]=='H') continue;
            if(visit[next_x][next_y]){
                printf("-1\n");
                exit(0);
            }
            else if(dp[next_x][next_y]<cnt+1){
                dp[next_x][next_y] = cnt+1;
                visit[next_x][next_y]=1;
                dfs(next_x, next_y, cnt+1);
                visit[next_x][next_y]=0;
            }
        }
    }
}
 
int main(){
    scanf("%d %d ",&N,&M);
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            scanf("%1c",&graph[i][j]);
        }
        char buf;
        scanf("%1c",&buf);
    }
    dp[0][0] = 1;
    visit[0][0]=1;
    dfs(0,0,1);
    printf("%d\n",ans);
}

 

처음에는 인풋이 작길래 아무생각없이 무작정 dfs로 들어가기만 했다

당연히 시간초과ㅋㅋㅋㅋ

그다음에는 visit과 별개로 dp를 만들어주었는데 이 때 dp 조건을 잘못 써서 계속 틀렸다

 

특정 위치에 가게 되면 어느쪽에서 오든 어차피 다시 반대방향으로 갈테니 dp 배열이 0이 아닌지만 확인하면 된다고 생각했는데

반례를 찾아보니 그게 아니었다

그래서 더 많이 이동할 수 있는 경우는 dp 배열을 갱신해주었다

 

지난번 삼성 sw 테스트에서도 느꼈는데 반례 찾는 연습이 필요할 것 같다