게임

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 1218 ~ 0128
// 백트래킹 + DP 풀이
int N, M, ans=1;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
char board[55][55];
map<pair<pair<int,int>,int>, bool> m; // Cycle을 찾기 위한 용도
map<pair<pair<int,int>,int>, int> dp; // 해당 좌표,방햐으로 이미 접근했는데 짧거나 같은 경로라면 굳이 할필요 X
void DFS(int y, int x, int cnt)
{
    for(int dir=0;dir<4;dir++)
    {
        int ny = y;
        int nx = x;
        int len = board[y][x] - '0';
        while(len--)
        {
            ny += dy[dir];
            nx += dx[dir];
        }
        /* 보드판을 넘어가거나 구멍을 만나면 종료 */
        if((nx<0 or ny<0 or ny>=N or nx>=M) or (board[ny][nx] == 'H')){
            dp[{{ny,nx},dir}] = max(cnt+1, dp[{{ny,nx},dir}]);
            ans = max(ans,cnt+1);
            continue;
        }
        /* 해당 좌표에 해당 방향으로 왔다고 표시! */
        if(m[{{ny,nx},dir}] == true){
            cout << -1;
            exit(0);
        }
        /* 이미 해당 좌표에 해당 방향으로 온 경로보다 작으면 더이상 할 필요가 X */
        if(dp[{{ny,nx},dir}] >= cnt+2){
            continue;
        }
        dp[{{ny,nx},dir}] = cnt+2;
        m[{{ny,nx},dir}] = true;
        ans = max(ans,cnt+2);
        DFS(ny, nx, cnt+1);
        m[{{ny,nx},dir}] = false;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin >> board[i][j];
    for(int dir=0;dir<4;dir++)
    {
        int ny = 0;
        int nx = 0;
        int len = board[0][0] - '0';
        while(len--)
        {
            ny += dy[dir];
            nx += dx[dir];
        }
        /* 보드판을 넘어가거나 구멍을 만나면 종료 */
        if((nx<0 or ny<0 or ny>=N or nx>=M) or (board[ny][nx] == 'H')){
            dp[{{0,0},dir}] = 1;
            ans = max(ans,1);
            continue;
        }
        /* 해당 좌표에 해당 방향으로 왔다고 표시! */
        if(m[{{ny,nx},dir}] == true){
            cout << -1;
            exit(0);
        }
        /* 이미 해당 좌표에 해당 방향으로 온 경로보다 작으면 더이상 할 필요가 X */
        if(dp[{{ny,nx},dir}] >= 2){
            continue;
        }
        ans = max(ans,2);
        dp[{{ny,nx},dir}] = 2;
        m[{{ny,nx},dir}] = true;
        DFS(ny, nx, 1);
        m[{{ny,nx},dir}] = false;
    }
    cout << ans;
    return 0;
}

• 필요 기법
  • 백트래킹 + DP를 모두 사용해야 무한 경로 검사 + 중복 경우 제거(시간 단축)이 가능함!

• 핵심
  • Cycle 검사
    : map을 활용해서 해당 좌표의 해당 방향으로 이미 온 기록이 있으면 Cycle로 간주 (백트래킹 이용)
    --> 무한대로 도는 경우를 검사해서 -1 출력 후 exit(0)
  • 메모제이션 기법으로 중복 제거
    : 해당 좌표에 해당 방향으로 기록된 길이가 현재 경우보다 크거나 같으면 더이상 할필요가 X
    --> 중복을 배제하여 시간 단축!

• 느낀 점
  • cycle검사에 map을 유용하게 활용 가능
  • DP의 핵심인 메모제이션 기법을 통해서 중복을 배제할 수 있음 --> 시간 단축