[Baekjoon] 로봇 조종하기(BOJ 2169)

👀 문제 설명

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

 

출력

첫째 줄에 최대 가치의 합을 출력한다.

 

예제 입력 1

5 5

10 25 7 8 13

68 24 -78 63 32

12 -69 100 -29 -25

-16 -22 -57 -33 99

7 -76 -11 77 15

 

예제 출력 1

319

✍🏻풀이

앞에 푼 '[Baekjoon] 욕심쟁이 판다(BOJ 1937)'랑 똑같이 Dynamic Programming으로 푸는 문제.

이 문제는 무조건 (1, 1)에서 시작해서 (n, m)에서 끝난다는 점이 다른 것 같다고 생각했다.

비슷하게 풀면 된다고 생각해서 풀었는데 자꾸 오류가 난다 :(

 

[처음 생각한 방법]

1. n과 m을 입력받고, 크기만큼 mars[MAX][MAX]에 각 가치를 입력 받는다.

   이 때, dp[MAX][MAX]는 모두 0으로 초기화한다. (1, 1) 위치만 mars[1][1]과 같은 값으로 넣어준다.

   dp[MAX][MAX]는 dynamic programming을 통해 각 자리에서 가치의 최대 합을 저장해두는 용도..

2. dx[3]과 dy[3]을 이용하여 왼쪽, 오른쪽, 아래쪽으로 움직임 - for문 사용

3. max 함수를 사용해서 이동한 자리에서 dp[i][j]의 기존값과 새로운 값을 비교하여 더 큰 값을 dp[i][j]에 저장해둔다.

4. 이동한 자리에서 dynamic programming 실행

 

이런 식으로 풀었는데 자꾸 오류가 난다! ㅠ

아래는 틀린 코드 :(

 

틀린 코드

//
//  BOJ_2169.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/05/18.
//  Copyright © 2020 조수민. All rights reserved.
//
//  로봇 조종하기(https://www.acmicpc.net/problem/2169)

#include <stdio.h>
#include <iostream>
#define MAX 1000 // 1 <= N, M <= 1000

using namespace std;

int n, m;
int mars[MAX][MAX];
int dp[MAX][MAX]; // (1, 1)에서부터 (i, j)까지 이동했을 때 합이 최대가 되는 값들을 저장..?
int dx[3] = { 0, 0, 1 }; // (왼쪽, 오른쪽, 아래쪽)
int dy[3] = { -1, 1, 0 }; // (왼쪽, 오른쪽, 아래쪽)

void input()
{
    cin >> n >> m;
    
    for (int i = 0; i <=n; i++)
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = 0;
            
            if (i == 0 || j == 0)
                mars[i][j] = 0;
            else if (i == 1 && j == 1)
            {
                cin >> mars[i][j];
                dp[i][j] = mars[i][j]; // dp[1][1]에만 mars[1][1]과 같은 값을 넣어둔다.
            }
            else
                cin >> mars[i][j];
        }
}

int dynamic_programming(int x, int y)
{
    int now_answer = dp[x][y];
    
    // 오른족 아래(n, m)에 도착하면 (n, m)위치의 값을 더해 그 값을 return 한다.
    if (x == n && y == m)
        return now_answer + mars[x][y];
    
    for (int i = 0; i < 3; i++)
    {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        
        // 범위를 벗어나면 아래 구문을 수행하지 않고 다음번으로 넘어간다.
        if (next_x <= 0 || next_x > n || next_y <= 0 || next_y > m)
            continue;
        
        // 오른족 아래(n, m)에 도착하면 (n, m)위치의 값을 더해 그 값을 return 한다.
        if (next_x == n && next_y == m)
            return now_answer + mars[next_x][next_y];
        
        // 제대로 된 위치라면 ..
        // 이동해서 또 수행 ..?
//        int next_dynamic = dynamic_programming(next_x, next_y);
//        now_answer = max(now_answer, next_dynamic);
//        dp[next_x][next_y] = now_answer;
        dp[next_x][next_y] = max(now_answer, now_answer + mars[next_x][next_y]);
        dynamic_programming(next_x, next_y);
    }
    
    return now_answer;
}

int max_answer()
{
    int answer = dynamic_programming(1, 1);
    
    return answer;
}

int main()
{
    input();
    
    cout << max_answer() << endl;
    
    return 0;
}

구글링을 통해 알아낸 방법은, 이 문제는 dx, dy와 for문을 사용해 풀면 더 복잡하다는 것..

아래와 같이 해결했다!

 

상수 선언

#define MAX 1001 : 1 <= N, M <= 1000 이기 때문에 1001로 선언했다.

 

필요한 변수

int n, m : 지형을 나타내는 n과 m

int mars[MAX][MAX] : 각 지역들의 가치를 담은 배열

int dp[MAX][MAX] : (1, 1)부터 (i, j)까지 이동했을 때의 합이 최대가 되는 값들을 저장

int leftRightCompare[2][MAX] : i가 2부터 n일 때, dp[i][j]를 구하기 위해서는 비교를 해야 한다. 비교를 하기 위한 배열

 

알고리즘

최종 답은 dp[n][m]이 되기 때문에, dp[i][j]만 구하면 되는데.. 이게 너무 복잡하다 ㅠ

mars[i][j]와 dp[i][j]의 초기 형태는 이렇게 된다.

dp[i][j]를 채워넣으면 된다!

 

로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있다!

dp[i][j]에서 i가 1일 때를 보면,

이미 지나간 길은 되돌아갈 수 없기 때문에, j가 2~5(m)까지의 dp[i][j]값은 mars[i][j] + dp[i][j - 1]이 된다.

이것을 코드로 옮겨보면

// i = 1일 때
// 이미 지나온 길은 다시 가지 못하므로, 오른쪽으로 갈 수밖에 없다.
for (int j = 2; j <= m; j++)
    dp[1][j] = mars[1][j] + dp[1][j - 1];

이렇게 된다!

 

이제 문제는 i가 2부터 5(n)까지일 때인데, case를 둘로 나눌 수 있다.

case 1) 왼쪽 -> 오른쪽으로 이동하는 경우

case 2) 오른쪽 -> 왼쪽으로 이동하는 경우

그런데, 각각의 case에서 아래로 이동하는 경우와 또 비교를 해줘야 한다.

이 때 아래로 이동한다는 것은 예로 들자면,

'25'에서 아래로 이동하는 것은 '24'의 입장에서 위에서 온다는 뜻과 같다.

이걸 유의하고,

 

각각의 case에서 아래로 이동하는 경우와 비교를 해야 한다는 것은

case 1) 왼쪽 -> 오른쪽 이동

'24'까지 가는 방법에는 '10' -> '68' -> '24', 즉 왼쪽 -> 오른쪽으로 이동하는 방법과

'35' -> '24', 즉 위 -> 아래로 이동하는 방법이 있으므로, 이 두 방법 중 더 큰 값을 leftRightCompare[0][j]에 넣는다.

 

case 2) 오른쪽 -> 왼쪽 이동

위와 마찬가지로 '24'까지 가는 방법에는

'63' -> '32' -> '63' -> '-78' -> '24' 오른쪽 -> 왼쪽으로 이동하는 방법과

'35' -> '24' 위 -> 아래로 이동하는 방법이 있다. 이 둘 중 더 큰 값을 leftRightCompare[1][j]에 넣는다.

 

위 작업이 끝났다면, 마지막으로 case 1과 case 2를 비교해 더 큰 값을 dp[i][j]에 넣어주면 된다!

 

다시 정리하면, 

1. case 1) 왼쪽 -> 오른쪽 이동시 max(왼 -> 오, 위 -> 아래) 한 값을 leftRightCompare[0][j]에 대입
2. case 2) 오른쪽 -> 왼쪽 이동시 max(오 -> 왼, 위 -> 아래) 한 값을 leftRightCompare[1][j]에 대입
3. leftRightCompare[0][j]와 leftRightCompare[1][j]를 비교, 더 큰 값을 dp[i][j]에 대입

이 된다.

이걸 코드로 옮기면 아래와 같다!

// i = 2~n일 때
// case 1) leftRightCompare[0][j]는 왼쪽 -> 오른쪽으로 이동했을 때
// case 2) leftRightCompare[1][j]는 오른쪽 -> 왼쪽으로 이동할 때
// case 1과 case 2의 값을 비교해 더 큰 값을 dp[i][j]에 넣는다.
for (int i = 2; i <= n; i++)
{
    // case 1) 왼쪽 -> 오른쪽 이동했을 때
    leftRightCompare[0][0] = dp[i - 1][1]; // 제일 처음 값은 위에서 내려온 값
    
    // 왼쪽 -> 오른쪽 오는 값 vs 위에서 내려오는 값 비교, 큰 값을 넣어준다.
    for (int j = 1; j <= m; j++)
        leftRightCompare[0][j] = max(leftRightCompare[0][j - 1], dp[i - 1][j]) + mars[i][j];
    
    // case 2) 오른쪽 -> 왼쪽 이동했을 때
    leftRightCompare[1][m + 1] = dp[i - 1][m]; // 제일 마지막 값은 위에서 내려온 값
    
    // 오른쪽 -> 왼쪽 오는 값 vs 위에서 내려오는 값 비교, 큰 값을 넣어준다.
    for (int j = m; j >= 1; j--)
        leftRightCompare[1][j] = max(leftRightCompare[1][j + 1], dp[i - 1][j]) + mars[i][j];
    
    // case 1과 case 2 값 비교
    for (int j = 1; j <= m; j++)
        dp[i][j] = max(leftRightCompare[0][j], leftRightCompare[1][j]);

 

이제 이 코드들을 합치면 끝 😭

 

코드

//
//  BOJ_2169.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/05/18.
//  Copyright © 2020 조수민. All rights reserved.
//
//  로봇 조종하기(https://www.acmicpc.net/problem/2169)

#include <iostream>
#define MAX 1001 // 1 <= N, M <= 1000

using namespace std;

int n, m;
int mars[MAX][MAX] = { 0 };
int dp[MAX][MAX] = { 0 }; // (1, 1)에서부터 (i, j)까지 이동했을 때 합이 최대가 되는 값들을 저장
int leftRightCompare[2][MAX] = { 0 };

void input()
{
    cin >> n >> m; // n,m 입력받기
    
    // mars[i][j]를 입력받는다.
    for (int i = 1; i <=n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mars[i][j];
    
    // (1, 1)에서 시작하므로 (1, 1)은 꼭 들어가야 하는 값
    dp[1][1] = mars[1][1]; // dp[1][1]은 mars[1][1]과 같은 값으로 초기화해둔다.
}

int getMax()
{
    // i = 1일 때
    // 이미 지나온 길은 다시 가지 못하므로, 오른쪽으로 갈 수밖에 없다.
    for (int j = 2; j <= m; j++)
        dp[1][j] = mars[1][j] + dp[1][j - 1];
    
    // i = 2~n일 때
    // case 1) leftRightCompare[0][j]는 왼쪽 -> 오른쪽으로 이동했을 때
    // case 2) leftRightCompare[1][j]는 오른쪽 -> 왼쪽으로 이동할 때
    // case 1과 case 2의 값을 비교해 더 큰 값을 dp[i][j]에 넣는다.
    for (int i = 2; i <= n; i++)
    {
        // case 1) 왼쪽 -> 오른쪽 이동했을 때
        leftRightCompare[0][0] = dp[i - 1][1]; // 제일 처음 값은 위에서 내려온 값
        
        // 왼쪽 -> 오른쪽 오는 값 vs 위에서 내려오는 값 비교, 큰 값을 넣어준다.
        for (int j = 1; j <= m; j++)
            leftRightCompare[0][j] = max(leftRightCompare[0][j - 1], dp[i - 1][j]) + mars[i][j];
        
        // case 2) 오른쪽 -> 왼쪽 이동했을 때
        leftRightCompare[1][m + 1] = dp[i - 1][m]; // 제일 마지막 값은 위에서 내려온 값
        
        // 오른쪽 -> 왼쪽 오는 값 vs 위에서 내려오는 값 비교, 큰 값을 넣어준다.
        for (int j = m; j >= 1; j--)
            leftRightCompare[1][j] = max(leftRightCompare[1][j + 1], dp[i - 1][j]) + mars[i][j];
        
        // case 1과 case 2 값 비교
        for (int j = 1; j <= m; j++)
            dp[i][j] = max(leftRightCompare[0][j], leftRightCompare[1][j]);
    }
        
    return dp[n][m];
}

int main()
{
    input();
    
    cout << getMax() << endl;
    
    return 0;
}

---

이거 하루종일 잡고 있었다..😭 DP 너무 어렵다.. 금방 풀 줄 알았는데 .. :(

[참고] 블로그