[Algorithm]Baekjoon 2169번 :: 로봇 조종하기

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

2169번: 로봇 조종하기

 
 
using namespace std;
 
 
int n, m;
int arr[1005][1005] = { 0 };
int rightDP[1005][1005] = { 0 };
int leftDP[1005][1005] = { 0 };
int dp[1005][1005] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 1; i <= m; ++i)
    {
        dp[1][i] = dp[1][i - 1] + arr[1][i];
    }
 
    for (int i = 2; i <= n; ++i) // 2번째 행부터 로직 진행.
    {
        for (int j = 1; j <= m; ++j) // 윗값(dp[i-1][j]를 먼저 반영.
        {
            rightDP[i][j] = dp[i - 1][j] + arr[i][j];
            leftDP[i][j] = dp[i - 1][j] + arr[i][j];
        }
 
        for (int j = 2; j <= m; ++j)
        {
            rightDP[i][j] = max(rightDP[i][j], rightDP[i][j - 1] + arr[i][j]);
        }
 
        for (int j = m-1; j >= 1; --j)
        {
            leftDP[i][j] = max(leftDP[i][j], leftDP[i][j + 1] + arr[i][j]);
        }
 
        for (int j = 1; j <= m; ++j)
        {
            dp[i][j] = max(rightDP[i][j], leftDP[i][j]);
        }
    }
 
    cout << dp[n][m];
}
 

 

골드2 dp는 일단 건너뛰려했는데, 문제유형이 딱 스탠다드한 유형이라서 꼭 풀어봐야겠다고 생각해서 풀어봤다.

Top-Down으로 하다가 Bottom-Up으로 시도했는데, 아이디어 방향은 맞았는데 끝까지 정해에 도달하진 못했다..

특정칸에 좌측에서 접근했을 때와 우측에서 접근했을 때를 따로 dp배열을 둬야할것같다는 생각까지만 도달했다.

 

참고한 풀이는 아래와 같으며, Top-Down방식과 Bottom-Up방식 둘 다 친절하게 설명되어있다.

이런 풀이하는 글 작성하는것도 진짜 오래걸리는데, 대단하신 것 같다. 사실상 배보다 배꼽이 더 크지않을까..

https://yabmoons.tistory.com/559

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

 

 

먼저 3개의 dp배열을 만든다. 나같은 경우 각각 rightDP, leftDP, 그냥 DP 이렇게 3개를 선언했다.

rightDP는 해당칸에 '위나 왼쪽'에서 접근했을 때의 최대값을 저장한다.

leftDP는 해당칸에 '위나 오른쪽'에서 접근했을 때의 최대값을 저장한다.

DP는 해당칸의 최종적인 최대값을 저장한다. (문제의 조건처럼, 왼쪽,위,오른쪽에서 접근했을 때의 최대값).

 

먼저 DP배열의 첫번째 행에는 arr값의 첫행 첫열값을 오른쪽으로 쭉 누적시킨다.

첫행의 각 열에 대해서는, 접근할 방법이 각 칸의 왼쪽밖에 없기때문에 오른쪽으로 누적시킨것이 정해인 DP값이다.

 

이후 두번째 행부터 본격적인 로직을 수행한다.

먼저 첫번째 열부터 m번째 열까지, rightDP와 leftDP의 각 열에 dp[i-1][j] + arr[i][j]값을 넣어준다.

오른쪽에서 접근하든 왼쪽에서 접근하든, 기본적으로 위에서 접근하는건 동일하다. 그렇기 때문에 미리 위에서 접근하는 값인 dp[i-1][j] + arr[i][j]값을 넣어준다. 바로 윗칸의 최대값인 dp[i-1][j]와 현재칸의 값인 arr[i][j]를 더해준것이다.

 

이후에 각 방향에서의 DP배열을 최대값갱신 해준다.

먼저 rightDP, 즉 왼쪽에서 접근하는 최대값부터 갱신해주는데 이 때 j값을 1부터가 아닌 2부터 진행해야한다. 

왜냐하면 현재 rightDP는 모든 원소의 값이 0으로 초기화되어 있기 때문이다. 

 

이 문제에서 배열의 원소는 -100 ~ 100인 정수값이 주어지기 때문에, 최대값을 갱신하는식의 로직을 하려면 처음에 미리 배열의 외각부분들에 대한 값을, 발생할 수 있는 최저값보다 더 낮은 수로 초기화시켜 놔야 한다.

초기화 시켜놨다면 1부터 시작해도 된다. 그러면 rightDP[0][1]이라던가 rightDP[1][0]에는 굉장히 작은값이 들어있으니, 어차피 최대값 갱신할 때 반영될 일이 없다.

현재 인풋값크기로는 하나 안하나 큰 차이는 없다만, 그냥 2부터 시작하면 되는걸 굳이 1부터 시작하겠다고 배열의 외각크기만큼 초기화하는 과정을 거칠필요가 없으니 2부터 시작한다.

 

leftDP를 업데이트하는 과정도 똑같다. 마찬가지로 오른쪽에서부터 특정칸에 접근하며 업데이트할건데, 사서 고생할필요 없이 m-1부터 시작하면 된다.

 

해당 '행'의 각 '열'에 대해서 rightDP, leftDP를 전부 업데이트했다면, 최종적으로 dp[i][j]에다가 둘 중 큰값을 넣어주면 끝이다. 이번 행에서 업데이트한 dp값을 토대로, 다음행에서 똑같은 로직을 수행할 것이다.

 

 

사실 Bottom-Up으로 봤을 때는 골드2인거 같긴한데, Top-Down방식의 코드짜는건 좀 더 쉽게 생각할 수 있는 문제인 것 같았다. 이정도는 좀 쉽게 풀었어야 했는데, 아직 실력이 좀 부족한 것 같다.

 

Top-Down은 아래와 같이한다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int MAX_NUM = -2000000000;
int n, m;
int arr[1000][1000] = { 0 };
int dp[1000][1000][3] = { 0 };
bool visited[1000][1000] = { false };
int dirs[3][2] = { {1,0}, {0,-1}, {0,1} };
 
int DFS(int y, int x, int dir)
{
    if (y == n - 1 && x == m - 1) return arr[y][x];
    if (dp[y][x][dir] != MAX_NUM) return dp[y][x][dir];
 
    int result = MAX_NUM;
 
    for (int i = 0; i < 3; ++i)
    {
        int nextY = y + dirs[i][0];
        int nextX = x + dirs[i][1];
 
        if (nextY < 0 || nextY == n) continue;
        if (nextX < 0 || nextX == m) continue;
        if (visited[nextY][nextX]) continue;
 
        visited[nextY][nextX] = true;
        result = max(result, DFS(nextY, nextX, i));
        visited[nextY][nextX] = false;
    }
 
    return dp[y][x][dir] = result + arr[y][x];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> arr[i][j];
 
            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = MAX_NUM;
        }
    }
 
    visited[0][0] = true;
    cout << DFS(0, 0, 0);
}

 

여기서 dp[y][x][dir]은 다음과 같다.

 

dp[y][x][dir] ==>

      (y,x)칸에 dir방향으로 들어'왔'을 경우, (y,x)칸부터 목적지(n-1, m-1)칸까지 이동할 때 최대값.

 

나같은 경우 방향을 아래,왼쪽,오른쪽 순서로 각각 0,1,2로 해놨다.

그러면 dp[4][0][0]의 값은,  (4,0)칸에 '아랫방향'으로 들어왔을 때, 목적지까지 이동할 때 최대값을 의미한다.

헷갈리지 말아야할 것은, (4,0)칸에서 '아랫방향'으로 뻗었을 때, 목적지까지의 최대값이 아니라는 것이다.

뻗는다는 걸로 표현해버리면 애초에 DFS(0,0,0)으로 바로 답 못구한다. 바로 1,0으로 이동해버려서 첫행첫열의 값들을 지나쳐버리까.

물론 기준을 뻗는다는걸로 하면 코드자체가 달라지겠지만 말이다.

 

그러면 들어왔을 떄 코드, 즉 위의 코드로 할 경우 왜 DFS(0,0,0)이 바로 답을 도출하는가?

DFS(0,0,0)은 결국 dp[0][0][0]을 리턴한다. 즉, (0,0)에 '아랫방향'으로 들어왔을 경우 목적지까지의 최대값을 의미한다.

그러니 그대로 쭉쭉 뻗어서 목적지까지가서 값을 계속 누적리턴받아서 출력하면 된다.

 

이것은 '오른쪽방향'으로 들어왔을 경우도 마찬가지다. 그래서 DFS(0,0,0)이 아닌 DFS(0,0,1)로 해도 정답이다.

근데 '왼쪽방향'으로 들어왔을 경우도 마찬가지다. 즉, DFS(0,0,2)로 해도 정답이다.

근데 시작지점은 무조건 0,0인데, 0,0에서 왼쪽방향으로 들어오는 경우를 정답으로 표현하는게 맞는건가..? 라는 의문이 들 수도 있다. (나는 경험이 부족해서 좀 헷갈렸다.)

 

사실 상관없는게, 시작지점이 아닌 다른칸에서는 특정칸의 왼쪽으로 가기전에 특정칸을 방문처리해버리기 때문에 다시 특정칸을 재방문하지 않는다. 즉, 특정칸으로 뻗어나갈 수 없다.

근데 시작지점인 0,0을 왼쪽방향으로 들어왔다고 가정하더라도 (0,0,2),  0,0의 오른쪽인 0,1이 방문표시가 안되어있기 때문에 쭉쭉 뻗어나갈 수 있다.