[C++][백준 1103] 게임

문제설명은 더보기를 눌러주세요

문제링크 : www.acmicpc.net/problem/1103

1103번: 게임

 

문제

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

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

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

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

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

입력

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

출력

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

 

-풀이-

어렵다. 
직전 정점 -> 현재 정점만 판단해주면 될 것 같아서
처음엔 BFS로 가능할 것 같아서 짰다가 

6 7
12HHHHH
2214HHH
H1HHHHH
H4H9H2H
HHHHHHH
HHH2HHH

이 반례에 무너졌다.
정답 : 6인가 7인가.. 그런데 내 답은 -1이었다. 
직전 정점만 볼 것이 아니라 과정 중 사이클이 있는지 판단해야된다.

DFS를 돌면서 cycle이 있는지 판단하는 문제.
하지만 그냥 판단해선 안되고(시간초과) 꼭 DP를 사용해야한다.
코드만 보면 쉬운 것 같은데 이 간단한 코드를 못짰다.
어렵다 어려워.. 다음에 다시 봐야겠다.
sejinik.tistory.com/190 이 블로그를 참고했다.

 

-코드-

#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 100000000
using namespace std;
int DFS(int x, int y);
int N, M, ans=0, map[51][51], dp[51][51], visit[51][51];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main(){
    memset(dp, -1, sizeof(dp));
    memset(visit, 0, sizeof(visit));
    string str;
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        cin >> str;
        for(int j=0; j<str.size(); j++){
            if(str[j] == 'H') map[i][j+1] = 0;
            else map[i][j+1] = str[j]-'0';
        }
    }
    int ans = DFS(1, 1);    
    if(ans >= INF) cout << "-1";
    else cout << ans;
    return 0;
}

int DFS(int x, int y){
    if(visit[x][y]) return INF;
    int& ret = dp[x][y];
    if(ret != -1) return ret;
    ret = 1;

    visit[x][y] = 1;
    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 < 1 || ny < 1 || nx > N || ny > M || map[nx][ny] == 0) continue;
        ret = max(ret, DFS(nx, ny)+1);
    }
    visit[x][y] = 0;
    return ret;
}