[ Baekjoon - 11/07 ] - 2169번: 로봇 조종하기

• 문제 링크 : https://www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

 

• 소요 시간 : 거의 4시간? 정도.. 

로봇 조종하기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

12267

4279

2943

33.855%

문제

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

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     
     • N x M 맵(1 ≤ N, M ≤ 1,000)의 칸마다 탐사가치가 있음(0 ≤ 탐사가치 ≤ |100|)
     • 맵에서 로봇을 (1,1)부터 (N,M)로 옮기려 하는데, 로봇은 좌측, 우측, 아래로 움직일 수 있다.
     • 얻을 수 있는 탐사가치의 최댓값을 출력하는 문제
   • 이해
     • 문제 자체는 단순해 보였지만, 조건을 따지려 분석했을땐 쉽지 않았다..
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 해당 조건을 단순히 적어보았고, 시간과 메모리공간에 따라 문제를 분석해보았다.
3. 문제를 어떻게 해결할 것인가

   • 

   • 1st 접근 - 완탐)
     • 우선 완탐으로 가능할지 부터 생각했다. 
     • 위 로봇은 위로는 못갈뿐 우측, 좌측, 아래로 갈 수 있으므로, BFS로 하기에는 방문처리가 굉장히 난해해 질것이라 판단하여, DFS로 작성해야한다고 생각했다.
     • 하지만, N과 M은 각각 1000보다 같거나 작은 값이기 때문에 DFS를 돌리면 O(N!)이 되므로 불가능했다.
   • 2nd 접근 - 누적합 1개 : 좌측에서 우측으로 더하기)
     • 완탐을 쓸 수 없고, 그렇지만 맵은 크지만 시간은 1초이고, 메모리 제한은 넉넉한 값을 주어서 dp적인 접근을 해야한다고 생각했다. 그 중 첫번째가 누적합이었다.
     • 로봇은 위로는 가지 못하므로 한 행씩 내려오면서 누적합해둔값을 이용해 더해가면서 판단하면 될것이라 생각했었다.
     • 하지만 식을 어떻게 세워야할지 감이 안잡힐 정도로 난해해서 누적합을 하나 더 만들어 점화식을 간결화 시키고자 했다..
   • 3rd 접근 - 누적합 2개 : 좌측에서 우측, 우측에서 좌측 2개)
     • 누적합을 하나 더 추가해서 점화식을 어떻게 세워야할지 고민해보았는데, 사실상 큰 문제가 있었다.
     • 우측으로만 가는것이 아닌 좌측으로도 갈수있기 때문에, 돌아오는 경우 가기만하는 경우들을 복합적으로 생각해야했기때문에 열심히 고민했지만.. 결국 제대로된 식을 얻지 못했다.
     • 그나마 얻은 생각이 위 사진의 ④번 부분처럼 한줄한줄 내려오면서 m이 1일때는 |, | |, | | |, | | | | ... 식의 합중 최댓값, m이 2일때는 ㄱ, ㄱ|, ㄱ| |, ㄱ| | | ..., m이 3일때는 ㅡㄱ, ㅡㄱ| |, ㅡㄱ | | | ... 형태를 더하면 된다고 생각했다. 
     • 그렇지만 좌측에서, 우측에서 올 수 있기 때문에 케이스가 너무 난해해졌고 좀더 단순화 시키고 싶다고 생각했다.
   • 4th 접근 - 좀 더 dp적으로.. 해당 좌표로 올수있는 최댓값을 저장하기)
     • 3번째 접근까지 생각하고나니 꽤 많은 시간이 흘러있어서.. 도움을 얻고자 알고리즘 분류를 보았는데 dp였다. dp라는 접근법이 맞긴해도 내가 접근한 방법보다 좀더 간결하게 dp를 정리할 수 있을것같아.. 결국 구글링을 좀 했다.
     • 좌측에서, 우측에서, 위쪽에서 오는 값들중 최댓값을 저장하는 방식으로 가면 된다는 문장을 보고 직접 코드로 구현하기위해 생각을 쏟았다.
     • 우선 좌측부터 생각해보면 
       좌측에서 왔다는 말은 현 좌표가 dp[n][m]일때, 전 좌표는 dp[n][m-1]일 것이다. 즉, 전 좌표가 어떻게 왔는지를 생각하면 된다.
     • 전 좌표는 로봇 방향에 따라 좌측, 우측, 위쪽에서 왔을것이다.
       그런데 "좌측 -> 좌측 -> 현 좌표", "위쪽 -> 좌측 -> 현 좌표"의 경우 가능하지만 우측 -> 좌측 -> 현좌표의 경우 결국 제자리 걸음이고 이미 정산된(포함된) 탐사 가치이므로 제외해주어야한다.
       즉, dp[n][m] 좌측 최댓값 = dp[n][m-1]의 왼쪽에서 온값과 위쪽에서 온 값중 최댓값 + (n,m)의 탐사가치.
     • 마찬가지로 우측에서 온 좌표의 경우도, 좌측에서는 제외해주어야하므로, 
       dp[n][m] 우측 최댓값 = dp[n][m + 1]의 우측에서 온값과 위쪽에서 온 값중 최댓값 + (n,m)의 탐사가치.
     • 그러면 위쪽에서 온 좌표의 경우는, 우측에서든 좌측에서든, 위쪽에서든 오는 경우가 가능하므로
       dp[n][m] 위쪽 최댓값 = dp[n-1][m]의 우측에서 온값과 좌측에서 온 값 그리고 위쪽에서 온 값 중 최댓값 + (n,m)의 탐사가치 이다.
     • 그러면 어떻게 dp의 좌측, 우측, 위쪽 최댓값을 보관할 수 있을지 생각해야하는데, 단순하게 3차원 배열을 만들어버리면 가능해진다.
4. 위 계획을 검증
   • 문제가 생긴다면, dp를 생성할 때 값이 없는 곳(혹은 초기값)을 더해버려서 값이 꼬이는 경우인데, 그것만 피해주면 무난히 실행될 수 있다. 그리고 이건 코드적으로 해결해야할 문제임.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int N, M;
            static int[][][] dp;
            static int[][] w;
        
            public static void main(String[] args) throws Exception {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
                StringTokenizer st = new StringTokenizer(br.readLine());
                N = Integer.parseInt(st.nextToken());
                M = Integer.parseInt(st.nextToken());
        
                // 해당 좌표로 왼,위,오 방향에서 올때의 최대값
                dp = new int[N + 1][M + 1][3];
                w = new int[N + 1][M + 1];
        
                for (int n = 0; n <= N; n++) {
                    for (int m = 0; m <= M; m++) {
                        dp[n][m][0] = dp[n][m][1] = dp[n][m][2] = -101 * N * M;
                    }
                }
        
                for (int n = 1; n <= N; n++) {
                    String[] strings = br.readLine().split(" ");
                    for (int m = 1; m <= M; m++) {
                        w[n][m] = Integer.parseInt(strings[m - 1]);
                    }
                }
        
                dp[1][1][0] = dp[1][1][1] = dp[1][1][2] = w[1][1];
                for (int n = 1; n <= N; n++) {
                    for (int m = 1; m <= M; m++) {
                        if (m > 1)
                            dp[n][m][0] = Math.max(dp[n][m - 1][0], dp[n][m - 1][1]) + w[n][m];
                        if (n > 1)
                            dp[n][m][1] = Math.max(dp[n - 1][m][0], Math.max(dp[n - 1][m][1], dp[n - 1][m][2])) + w[n][m];
                    }
                    for (int m = M - 1; m >= 1; m--) {
                        dp[n][m][2] = Math.max(dp[n][m + 1][1], dp[n][m + 1][2]) + w[n][m];
                    }
                }
                bw.write(Math.max(dp[N][M][0], dp[N][M][1]) + "\n");
                bw.flush();
            }
        }

   2. Python 3

      • import sys
        input = sys.stdin.readline
        
        def solution():
            N, M = map(int, input().split())
            initValue = -101 * N * M
            # 해당 좌표로 0:왼,1:위,2:오 방향에서 올때의 최대값
            dp = [[[initValue for _ in range(3)] for _ in range(M+1)] for _ in range(N+1)]
            val = [[0 for _ in range(M+1)] for _ in range(N+1)]
            for i in range(1, N+1):
                val[i] = [0] + list(map(int, input().split()))
        
            dp[1][1][0] = dp[1][1][1] = dp[1][1][2] = val[1][1]
            for n in range(1,N+1):
                for m in range(1,M+1):
                    if m > 1:
                        # 왼쪽에서 해당좌표로 온 경우의 최댓값 =  전 좌표의 왼쪽,위쪽 중 최댓값 + 해당좌표값
                        dp[n][m][0] = max(dp[n][m - 1][0], dp[n][m - 1][1]) + val[n][m]
                    if n > 1:
                        # 위쪽에서 해당좌표로 온 경우의 최댓값 =  전 좌표의 왼쪽,위쪽,오른쪽 중 최댓값 + 해당좌표값
                        dp[n][m][1] = max(dp[n - 1][m][0], max(dp[n - 1][m][1], dp[n - 1][m][2])) + val[n][m]
                for m in range(M - 1, 0, -1):
                    # 위쪽에서 해당좌표로 온 경우의 최댓값 =  전 좌표의 위쪽,오른쪽 중 최댓값 + 해당좌표값
                    dp[n][m][2] = max(dp[n][m + 1][1], dp[n][m + 1][2]) + val[n][m]
            print(max(dp[N][M][0], dp[N][M][1]))
        
        if __name__ == '__main__':
            solution()

6. 회고하기
   • 최근들어 3차원 dp나 vis배열을 사용해야하는 문제를 자주 만나고 있지만, 온전히 내 생각으로
     배열을 3차원으로 만들어야겠다는 생각은 못하는 것 같다... dp 자체도 점화식 너무 못세우기도하고ㅠ
   • dp나 vis배열이나 다 2차원일 것이라는 고정관념인 것 같기도한데, 생각을 뿌수고싶다.
   • 이 문제 이후로도 3차원이나 독특한 형태의 배열을 만들 문제도 많이 겪게 될테니.. 공식화된 생각이 아닌, 유연한 사고를 하도록 노력하고자 한다.
   • 언제쯤 되려나..

 

• 결과