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

백준의 게임(1103) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 게임판 위에서 동전을 최대 몇 번 움직일 수 있는지 구해야 하는 문제이다.

   본인은 이 문제를 DFS + DP 로 구현해보았다.

   단순 BFS 혹은 DFS로 접근할 경우, 중복된 지점에 방문 체크를 해주는 부분이 너무 까다롭고 시간초과에 걸리기 때문이다.

   먼저 본인이 이 문제를 구현하기 위해서 선언한 변수들부터 알아보자.

   1. bool Visit[][]. 방문처리를 위한 Visit배열이다. 현재 탐색 경로로 진행되다가 이미 방문처리된 좌표에 다시 돌아오게

     될 경우, 싸이클이 생겼다 판단하고 -1을 출력 후 그대로 종료시킨다.

   2. int DP[][]. DP[x][y] = a 의 의미는, (x, y)에서는 최대 a번 움직일 수 있습니다 를 의미한다.

     본인은 DP배열을 초기에 -1 값으로 초기화 시켜주었는데, 만약 탐색 하다가 특정 좌표의 DP 값이 -1이 아니라면

     기존에 방문한 적이 있다는 의미이고, 기존의 방문을 통해서 최대 몇 번 움직일 수 있는지 DP배열에 저장되어 있으므로

     더 이상의 탐색 없이 그대로 DP값을 return 해 주었다.

 

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
int DP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string S; cin >> S;
        for (int j = 0; j < S.length(); j++)
        {
            if (S[j] == 'H') MAP[i][j] = 0;
            else MAP[i][j] = S[j] - '0';
        }
    }
}
 
int DFS(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= M || MAP[x][y] == 0) return 0;
    if (Visit[x][y] == true)
    {
        cout << -1 << endl;
        exit(0);
    }
    if (DP[x][y] != -1) return DP[x][y];
 
    Visit[x][y] = true;
    DP[x][y] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + (MAP[x][y] * dx[i]);
        int ny = y + (MAP[x][y] * dy[i]);
        DP[x][y] = Bigger(DP[x][y], DFS(nx, ny) + 1);
    }
    Visit[x][y] = false;
    return DP[x][y];
}
 
void Solution()
{
    memset(DP, -1, sizeof(DP));
    Answer = DFS(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}