[백준 1103번 C++] Gold2. 게임

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

핵심 아이디어 및 정답 코드

- 게임을 진행하면서 최대로 이동할 수 있는 횟수가 몇인지 구하는 문제

 -> 모든 경우의 수를 구해야 하므로, 깊이 우선 탐색(DFS)를 이용

  -> 단, 이미 왔던 좌표라면 무한 루프를 돌 수 있으므로 -1를 리턴 (BackTracking)

 

- 모든 경우의 수를 구하다보면 중복 연산이 많아질 수 있음

 -> 동적 계획법(DP)을 통해 중복되는 연산을 줄임

 

즉, DP + DFS BackTracking 문제

 

+ 영역을 벗어거나 구멍에 의해 동전이 떨어지는 좌표로 이동하는 것도 이동횟수

 

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

정답 코드

#include <iostream>
#include <vector>
using namespace std;

int dirY[4] = { 0, 0, 1, -1 };
int dirX[4] = { 1, -1, 0, 0 };

int maxPosY, maxPosX, answer;
vector<vector<bool>> boolVecs;  // 방문배열
vector<vector<int>> intVecs;    // 동전배열 (H = 0)
vector<vector<int>> dp;         // dp배열

int DFS(int y, int x)
{
    if (dp[y][x] != 0)
        return dp[y][x];

    boolVecs[y][x] = true;
    for (int i = 0; i < 4; i++)
    {
        int movePosY = y + (dirY[i] * intVecs[y][x]);
        int movePosX = x + (dirX[i] * intVecs[y][x]);

        // 범위체크
        if (movePosY < 0 || movePosY >= maxPosY || movePosX < 0 || movePosX >= maxPosX
            || intVecs[movePosY][movePosX] == 0)
            continue;

        // 무한루프
        if (boolVecs[movePosY][movePosX])
        {
            cout << -1;
            exit(0);
        }

        // DFS
        dp[y][x] = max(dp[y][x], DFS(movePosY, movePosX) + 1);
    }

    boolVecs[y][x] = false;
    return dp[y][x];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 초기 값 세팅
    cin >> maxPosY >> maxPosX;
    for (int y = 0; y < maxPosY; y++)
    {
        string str;
        cin >> str;

        vector<bool> boolVec(str.size(), false);
        vector<int> intVec(str.size(), 0);

        boolVecs.push_back(boolVec);
        dp.push_back(intVec);

        for (int x = 0; x < str.length(); x++)
            if (str[x] != 'H')
                intVec[x] = str[x] - '0';

        intVecs.push_back(intVec);
    }

    dp[0][0] = DFS(0, 0) + 1;
    cout << dp[0][0];
}