[ 백준 2169 ] 로봇 조종하기 (C++)

백준의 로봇 조종하기(2169) 문제이다.

[ 문제 바로가기 ]

[ 문제를 다시푸는 과정에서, 조금은 다른 방법으로 문제를 해결하여서 조금 더 구체적이고 다른 방법으로 포스팅

  하였습니다. 아래의 글을 읽으셔도 문제를 해결하는데 문제는 없지만 보다 구체적인 풀이 혹은 다른 풀이방법을

  원하시는 분들은 아래의 링크를 이용해 주시면 감사하겠습니다.

  [ 로봇 조종하기(2169) 다른풀이 보러가기 (Click) ]

]

 

[ 문제풀이 ]

1) 가장 왼쪽 위에서부터 가장 오른쪽 아래 까지 내려가면서 최댓값을 찾는 문제이다.

   이 문제를 단순 완전탐색으로 진행하게 되면, 최악의 경우 3^(1000 * 1000) 만큼의 계산을 요구하기 때문에

   시간초과가 발생하게 된다.

   그래서 본인은 메모이제이션을 이용해서 구현해 보았다. DFS와 DP를 합친 방식으로 구현을 했다.

   이를 위해서 3차원 배열을 하나 선언해주었다.

   int Cost[][][] 라는 배열인데, Cost[a][b][c] = d 의 의미는

   "(a, b)에 c방향으로 들어왔을 때, 최댓값은 d입니다." 를 의미한다.

   방향까지 넣어준 이유는, 같은 좌표라도 어떤 방향으로 들어왔는지에 따라서 당연히 계산해온 값이 다를 것이기 때문에

   이런 점을 고려해서 방향까지 넣어주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1000
#define R_INF -987654321
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
int Cost[MAX][MAX][3];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1 };
int dy[] = { 1, -1, 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++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int DFS(int x, int y, int Dir)
{
    if (x == N - 1 && y == M - 1) return MAP[x][y];
    if (Cost[x][y][Dir] != R_INF) return Cost[x][y][Dir];
 
    Visit[x][y] = true;
 
    int Biggest_Value = R_INF;
    for (int i = 0; i < 3; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < M)
        {
            if (Visit[nx][ny] == false)
            {
                Biggest_Value = Bigger(Biggest_Value, DFS(nx, ny, i));
            }
        }
    }
    Visit[x][y] = false;
    Cost[x][y][Dir] = MAP[x][y] + Biggest_Value;
    return Cost[x][y][Dir];
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            Cost[i][j][0] = R_INF;
            Cost[i][j][1] = R_INF;
            Cost[i][j][2] = R_INF;
        }
    }
    Answer = DFS(0, 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;
}