[-][BOJ-1103]게임

https://www.acmicpc.net/problem/1103

[접근방법]

다른 방법으로도 풀어야하는 문제

사이클 존재 유무 판정하기가 어려웠던 문제.

맵크기+1 보다 큰 게임수가 나타나면 사이클 존재한다고 판단.

하지만 이런 방식이 아닌 다른 방식으로 풀어야 속도가 훨씬 빨라짐을 알 수 있었음.

DFS + DP 방식으로 풀어야 훨씬 빠른 연산으로 풀어낼 수 있음.

[C++11 source Code BFS]

#include<cstdio>
#include<queue>
using namespace std;
const int M = 55;
const int dr[] = { 0,0,-1,1 };
const int dc[] = { -1,1,0,0 };
int INF;
int RO, CO;
 
char imap[M][M];
int vis[M][M];
 
 
struct pos {
    int r, c;
    int mov;
    pos() {}
    pos(int ir, int ic, int im) :r(ir), c(ic), mov(im) {}
};
 
void init() {
    for (int r = 0; r < M; r++) {
        for (int c = 0; c < M; c++) {
            vis[r][c] = -1;
        }
    }
}
 
int main() {
    scanf("%d%d", &RO, &CO);
    
    for (int r = 0; r < RO; r++) {
        scanf("%s", imap[r]);
    }
    init();
 
    pos start(0,0,1);
    queue<pos> Q;
    Q.push(start);
    int ans = -1;
    bool is_loop = false;
    INF = RO*CO + 1;
    while (!Q.empty()) {
        pos here = Q.front(); Q.pop();
 
        int hr = here.r;
        int hc = here.c;
        int hm = here.mov;
 
        if (vis[hr][hc] < hm) { // 현재 움직일 값보다 vis에 값이 작음.
            vis[hr][hc] = hm; // 값을 바꿈
            ans = (ans > hm) ? ans : hm; // 둘 중 더 큰 것을 저장
 
            if (ans > INF) is_loop = true;
        }
        else continue;
 
        if (is_loop) break;
 
        for (int i = 0; i < 4; i++) {
            int tm = imap[hr][hc] - '0'; // 이 칸에서 뛸 수 있는 크기
            int tr = hr + tm * dr[i]; // 다음 이동할 위치
            int tc = hc + tm * dc[i];
 
            if (tr < 0 || RO <= tr || tc < 0 || CO <= tc) continue; // range over
            
            if ('1' <= imap[tr][tc] && imap[tr][tc] <= '9') {
                Q.push(pos(tr, tc, hm + 1)); // 한번더 게임할 수 있음                
            }
        }
        
    }    
 
    if (is_loop) puts("-1");
    else printf("%d\n", ans);    
 
    return 0;
}