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

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

[ 문제 바로가기 ]

이 문제에 대한 풀이글을 기존에 작성한 글이 있는데, 그 글에서는 DFS + DP를 이용한 방식으로 문제를 해결하였다.

이번 글에서는 DP만을 이용한 풀이방법에 대해서 소개해보고자 한다.

[ 기존 글(로봇조종하기 - DFS + DP풀이) 바로가기 ]

[ 문제풀이 ]

하나의 예시를 가지고 문제에 한번 접근해보자.

그리고 지금부터는 수식을 하나 사용해서 문제를 표현해볼 것이다.

F[A][B] = C 라는 수식을 사용할 것인데, 이 수식의 의미는 "(A , B)까지 움직였을 때, 얻을 수 있는 최대가치는 C입니다." 를 의미한다. 즉 ! 우리가 정확하게 위의 수식을 모두 채웠다면 우리가 원하는 정답은 DP[N][M]에 저장되어 있을 것이다.

그럼 지금부터 이 수식을 어떻게 채워야하는지 알아보면서 채워가보자.

F[A][B] = C : (A , B)까지 움직였을 때, 얻을 수 있는 최대가치는 C원 입니다.

우리는 지금부터 다음과 같은 하나의 예시를 통해서 진행할 것이다.

.

그리고 탐색을 할 때, 하나의 조건을 달고 진행할 것이다.

바로, "아직 탐색하지 않은 좌표는, 미지의 좌표로써 함부로 계산하지 말자" 라는 조건이다.

무슨말인지 정확하게 몰라도 좋다. 진행하면서 천천히 알아보도록 하자.

#Case1 : 좌표 (1 , 1) 에서 얻을 수 있는 최대가치

로봇은 왼쪽, 오른쪽, 아래쪽 으로만 이동할 수 있다고 되어있다. 그럼 이 때, 시작 좌표인 (1 , 1)에서 얻을 수 있는 최대 가치는 얼마가 될까?? 바로 '1점'이 된다. 왜 ?? 로봇이 왼쪽, 아래쪽, 오른쪽으로 이동할 수 있다고 했는데, (1, 1) 이전의 좌표에서

(1 , 1 )로 올 수 있는 좌표는 존재하지 않기 때문이다.

(1 , 2)에서 왼쪽으로 움직이면 (1 , 1)로 올 수 있지 않을까 ?? 올 수는 있다. 그런데, 우리의 조건을 다시한번 생각해보자.

"아직 탐색하지 않은 좌표는, 미지의 좌표로써 함부로 계산하지 말자." (1 , 2)는 우리가 아직 한번도 탐색을 해본 적이 없는 미지의 좌표이다. 따라서, (1 , 2)까지 움직였을 때, 얻을 수 있는 최대가치를 우리는 모르는 상태이다.

그런데, (1 , 2)까지 움직였을 떄의 최대가치 + (1, 2)에서 왼쪽으로 움직여서 (1 , 1)로 왔을 때의 가치를 계산한다 ?

계산할 수 없는 부분이다. 따라서, (1 , 1)은 그 어떠한 계산도 할 수 없고, (1 , 1)이 가지고 있는 그 가치, '1'이 (1 , 1)에서 얻을 수 있는 최대가치가 된다.

F[1][1] = 1

그럼 지금부터는 시각적으로 보기 편하게, F[][]에 대한 맵도 본인이 하나 가져오겠다.

아직 계산이 되지 않은 미지의 좌표는 빈 칸으로 표시하겠다.

.

#Case2 : 가장 윗 줄에서 얻을 수 있는 최대가치

두 번째로 가장 윗줄로 넘어가보자. 가장 윗줄의 좌표들을 먼저 적어보면, (1 , 1), (1 , 2), (1 , 3), (1 , 4), (1 , 5) 이렇게 5개의 좌표가 존재한다. 그런데 우리는 Case1에서 (1 , 1)의 최대가치를 계산하였다.

그럼 나머지, (1 , 2) ~ (1 , 5)의 최대가치를 계산해보자.

먼저, (1 , 2)로 가보자. 어떤 좌표에서 왼쪽/아래쪽/오른쪽 으로 움직여서 (1 , 2)로 움직였을 때 얻을 수 있는 가치를 생각해보자.

1. 어떤 좌표에서 왼쪽으로 움직여서 (1, 2)로 간다면, 이는 (1 , 3)에서 왼쪽으로 움직여서 (1 , 2)로 가는 경우를 의미할 것이다.

2. 어떤 좌표에서 아래쪽으로 움직여서 (1 , 2)로 간다면, 이는 (0 , 2)에서 아래쪽으로 움직여서 (1 , 2)로 가는 경우를

의미할 것이다.

3. 어떤 좌표에서 오른쪽으로 움직여서 (1 , 2)로 간다면, 이는 (1 , 1)에서 오른쪽으로 움직여서 (1 , 2)로 가는 경우를

의미할 것이다.

먼저, 1번 경우는 우리가 정해놓은 '조건'에 위배되는 상황이다. 왜냐하면, (1 , 3)이라는 좌표는 아직 우리가 탐색한 적이 없는 미지의 좌표이다. 따라서 함부로 계산할 수가 없다.

2번 경우는 모순이 되는 상황이다. 왜냐하면, 우리가 진행하고 있는 맵에서 (0 , 2)라는 좌표는 존재하지 않는 좌표이기 때문이다.

3번 경우는 계산이 가능한 경우이다. (1 , 1)은 맵의 범위 내에도 존재하는 좌표이고, 이미 우리가 계산을 한번 해 본 적이 있는 미지의 좌표가 아니기 때문이다. 그리고 F[1][1] = 1 이라는 것 또한 우리는 알고 있다.

따라서, 3번 경우에 계산이 가능하게된다. 그럼 (1 , 1)에서 (1 , 2)로 왔다는 것을 의미하고, 이 때 (1 , 2) 좌표가 얻을 수 있는 최대 가치는 (1 , 1) + (1 , 2) = 3이 된다.

다른 (1 , 3) ~ (1 , 5)의 좌표도 똑같은 방식으로 계산된다. 더 오른쪽에 있는 좌표에서 왼쪽으로 움직이는 경우는 우리가 만들어 놓은 '조건'에 위배되어서 계산이 불가능하고, 더 위에 있는 좌표에서 아래족으로 움직이는 경우는 존재하지 않는 좌표들이 개입하게 되기 때문에 계산이 불가능하다.

즉 ! F[1][X] 에서 얻을 수 있는 최대가치는 F[1][X - 1] + MAP[1][X]가 된다.

F[1][x] = F[1][x - 1] + MAP[1][x]

따라서, 위에 계산한 대로 쭉 적어보면 다음과 같이 F[][] 값을 채울 수 있다.

.

(왼쪽은 원본맵 / 오른쪽은 F[][] 맵 입니다.)

#Case3 : 나머지 좌표들

이제 남은 좌표들을 쭉 채워볼 것이다.

Case2에서 진행했던, 가장 윗줄과 달리, 지금부터 할 나머지 좌표들은 가장 우선적으로 계산할 수 있는 방법이 하나 있다.

Case2에서 진행한 가장 윗줄은, "왼쪽 좌표에서 오른쪽으로 움직이는 경우" 만 계산이 가능했다면, 나머지 좌표들은 갈리게 된다. 어떤 좌표는 왼쪽에서 오른쪽으로 움직이는 경우가 불가능하고, 어떤 좌표는 오른쪽에서 왼쪽으로 움직이는 경우가 불가능 하고, 어떤 좌표는 어떻게 움직이더라도 모두 계산이 가능하다.

그런데 우리는 이 중에서 "가장 우선적으로 계산"이 가능한 경우를 알 수 있다. 바로 "위에 있는 좌표에서 아래쪽으로 움직이는 경우" 는 가장 우선적으로 계산이 가능하다.

왜냐하면, Case2에서 우리는 가장 윗줄을 모두 계산해 놓았기 떄문에, (1, x)에서 (2 , x)로 내려오는 것은 "미지의 좌표"에서 계산하는 것도 아니고, 맵의 범위 내에 있는 좌표에서 계산을 하는 것도 아니기 때문에 가장 우선적으로 계산이 가능하다.

그럼, 먼저 (2 , 1) ~ (2 , 5)의 좌표에 (1 , 1) ~ (1 , 5)에서 아래쪽으로 움직이는 경우라고 생각해보고, F[][]의 배열을 채워보자.

(2 , 1)은 (1 , 1)에서 내려올 것이다. 즉, (1 , 1)의 최대가치인 1 + (2 , 1)의 좌표값인 '5' 만큼을 가치로 얻을 수 있게 된다.

(2 , 2)는 (1 , 2)에서 내려올 것이다. 즉, (1 , 2)의 최대가치인 3 + (2 , 2)의 좌표값인 '4' 만큼을 가치로 얻을 수 있게 된다.

마찬가지로 쭉 계산해보면, 두 번째 줄의 F[][] 값을 다음과 같이 채울 수 있게 된다.

.

F[2][] 의 값이 위와 같이 채워진 현 상황에 대해서 조금만 더 구체적으로 말해보자면

우리는 현재 "상대적으로 위에 있는 좌표에서 아래쪽으로 움직임으로써 얻을 수 있는 최대가치를 계산" 한 상태이다.

즉 ! 그림으로 나타내보면 다음과 같이 왔기 온 것이다.

.

따라서 우리는 아래와 같이 F[][]의 값을 채울 수 있다.
.

그런데 ! 지금은 "위에서 아래쪽으로 움직이는 경우만 진행" 을 한 상태이다. 즉 ! 우리는 왼쪽에서 오른쪽으로 움직이는 경우, 오른쪽에서 왼쪽으로 움직이는 경우도 진행을 해줘야 한다.

가장 먼저, 가장 왼쪽 줄에 있는 좌표들은 "상대적으로 더 왼쪽에 있는 좌표에서, 오른쪽으로 움직임으로써 오는 경우" 가 불가능 하다. 왜냐하면, 가장 왼쪽 줄에 있기 때문에, 더 왼쪽에 있는 좌표는 맵의 좌표를 벗어나는 좌표들이기 때문에 계산이 불가능하다. 그럼 가장 왼쪽에 있는 좌표를 제외한 나머지 좌표, 즉, (2 , 2) ~ (2 , 5)에 대해서만 진행을 해보자.

어떤 좌표에서 오른쪽으로 움직여서 (2, 2)로 온다는 것은, 그 어떤 좌표는 (2 , 1)을 의미할 것이다.

따라서, 우리는 (2 , 1)에서 얻을 수 있는 최대가치 + (2 , 2) 좌표에서 얻을 수 있는 가치가 이 경우에 얻을 수 있는 (2 , 2)에서의 가치가 된다.

계산을 해보면, (2 , 1)에서 얻을 수 있는 가치 = 6이 되고, (2 , 2)에서 얻을 수 있는 가치 = 4 로써, 둘을 더하게 되면 10이 된다. 그런데, 우리가 기존에 구해놓은 (2 , 2)에서 얻을 수 있는 가치는 '7'이였다. 그런데 ! 다른 경로로 오니까 더 큰 가치를 얻을 수 있게 되었다. 따라서 값을 갱신해주는 것이다.

.

위의 그림과 같이 ! 기존의 경로와 현재 경로를 비교해서 그림으로 나타내면 다음과 같다.

.

기존에 (2 , 2)에서 우리가 구한 가치는 "빨강색 경로"로 움직일 경우 얻을 수 있는 가치였다.

저 경우에는 1 + 2 + 4 = 7 의 가치를 얻을 수 있었다.

그런데, 방금 우리가 계산한 경로는 "파랑색 경로" 이다. (2 , 1)에서 오른쪽으로 움직여서 (2 , 2)로 온 경우이고, (2 , 1)은

(1, 1)에서 아래쪽으로 내려온 경로인 것이다.

이 경우에는 1 + 5 + 4 = 10 의 가치를 얻을 수 있다. 따라서 가치를 갱신해주자.

마찬가지로 (2 , 3) ~ (2 , 5)도 똑같이 계산을 하면 다음과 같이 맵이 갱신되어진다.

.

여기까지 정리를 한번 해보자.

1. 우리는 2행에 존재하는 좌표들에 대해서 계산을 진행하였다.

2. 기존에 우리는 1행에 존재하는 좌표들에 대한 계산을 끝내놓았기 때문에, "위에서 아래로 내려오는 경우, 즉,

   1행에서 2행으로 움직이는 경우" 에 대해서 가장 우선적으로 계산을 할 수 있었다.

3. 가장 우선적으로 계산해서 2행에 모든 좌표들에 대한 1차적인 계산을 모두 끝냈다.

4. 왼쪽에서 오른쪽으로 움직이는 경우를 계산하기 위해서, 계산이 불가능한 (2 , 1)을 제외한 나머지 좌표들에

   대해서 계산을 진행하였더니 위와 같은 결과를 얻을 수 있었다.

그림 우리에게 남은 계산은 ? 이제 오른쪽으로 왼쪽으로 움직이는 경우만 남았다.

이 경우에는 역으로 (2 , 5)의 좌표는 계산이 불가능하다. 왜냐하면 어떤 좌표에서 왼쪽으로 움직여서 (2 , 5)로 온다면, 그 어떤 좌표는 (2 , 6)이여야 하는데, 그 좌표는 맵의 범위를 벗어나는 좌표이기 때문이다.

그럼 (2 , 1) ~ (2 , 4) 에 대해서 계산을 해보자.

그런데 이번에는 역순으로( (2 , 4)부터 ~ (2 , 1)의 순서로 ) 계산을 해주어야 한다. 왜 그럴까 ?? 일단 우리가 설정해 놓은 "조건"에 위배되는 상황은 아니다. 왜냐하면 (2 , 1) ~ (2 , 5)까지 모든 좌표가 이미 한 번 이상 계산된 좌표들이기 때문에 미지의 좌표라고 판단할 수는 없다. 그렇다고 맵의 범위를 벗어나는 좌표들도 아니다. 그런데 왜 역순으로 해줘야할까 ??

바로 "값의 갱신이 일어날 수 있기 때문" 이다. 하나의 상황을 예로 들어보자.

(2 , 1)을 오른쪽에서 왼쪽으로 오는 경우를 계산하기 위해서, (2 , 2)에서 얻을 수 있는 가치 + (2 , 1) 좌표의 가치로 계산을 했다고 가정해보자. 그럼 위의 그림대로라면, (2 , 2)에서 얻을 수 있는 가치는 10이고 , (2 , 1)의 좌표는 5 이기 때문에 15가 된다. 라고 설정이 될 것이다. 그런데 문제는, "만약, (2 , 3)에서 (2 , 2)로 움직이는 경우, 기존의 가치보다 더 커서, (2 , 2)의 가치가 새로운 가치로 갱신이 되어버린다면 ?" 과 같은 상황이 발생할 수 있다는 것이다.

즉, (2 , 2)는 분명히 "이미 한번 이상 계산된, 미지의 좌표가 아니다" 라는 것은 자명한 사실이다. 그런데 ! 그렇다고 "완벽하게 계산이 끝난, 더 이상의 값의 갱신이 발생할 수 없는 좌표" 라고도 말을 할 수는 없는 것이다. 왜 ? (2 , 3)에서 (2 , 2)로 오는 경우를 아직 계산을 안했기 때문이다. 그럼, 다른 좌표들에도 이 논리가 모두 적용될텐데 그럼 어떻게 계산을 할까 ??

2행에서 유일하게 "이미 완벽하게 계산이 끝난 좌표"가 딱 1개 존재한다. 바로, (2 , 5) 이다. 왜 ? (2 , 5)는 (2 , 6)에서 왼쪽으로 오는 경우 계산이 불가능한 좌표이기 때문이다. 그래서 우리는 이 좌표를 넘기고 (2 , 1) ~ (2 , 4)에 대해서만 계산을 하자고 이미 말도 해 놓은 상태이다.

따라서, (2 , 4)부터 역순으로 진행을 해야 하는 것이다.

그럼 계산을 해보자. (2 , 5)에서 (2 , 4)로 오는 경우는, (2 , 5)에서 얻을 수 있는 가치 + (2 , 4) 좌표에서 얻을 수 있는 가치 가 되는데, 이를 더해보면 16 + 2 = 18이 된다. 기존의 (2 , 4)에서 얻을 수 있는 가치인 '16'보다 더 큰 가치가 되므로 값을 갱신해주자. 마찬가지로, 나머지 좌표들에 대해서도 모두 계산을 한다면 다음과 같이 F[][] 맵이 새롭게 갱신된다.

.

지금 (2 , 1)에 갱신된 좌표만 보더라도 알 수 있듯이, (2 , 1)부터 계산했다면 절대로 '30'이라는 가치가 나오지 않았을 것이다. 하지만 모든 경우를 다 계산해보니 '30'이 된 것을 알 수 있다.

이렇게 해야, 한 행에 대해서 발생할 수 있는 모든 경우를 다 계산한 것이다.

지금까지 했던 Case1 ~ 3의 내용을 마지막으로 정리해보고 코드로 넘어가보자.

1. (1 , 1)은 예외적으로 계산을 먼저 진행해 주었다. [ F[1][1] = MAP[1][1] ]

2. 1행 또한 예외적으로 계산을 먼저 진행해 주었다. [ F[1][x] = F[1][x - 1] + MAP[1][x] ]

3. 2행부터 행의 순서대로 계산을 진행해 주었다.

4. 2행부터는 위쪽에서 내려오는 경우 / 왼쪽에서 오른쪽으로 오는 경우 / 오른쪽에서 왼쪽으로 오는 경우

   모두 가능하지만, 가장 우선적으로 "위쪽에서 내려오는 경우" 부터 진행해 주었다.

   왜냐하면 1행에 대한 계산을 모두 기존에 끝내놓았기 때문이다.

5. 왼쪽에서 오른쪽으로 오는 경우는, (2 , 1)을 제외한 나머지 좌표들에 대해서만 진행해주었다.

6. 오른쪽에서 왼쪽으로 오는 경우는, (2 , 5)를 제외한 나머지 좌표들에 대해서만 진행해 주었고,

   또한, 값의 올바른 갱신을 위해 역순으로 (2 , 4) ~ (2 , 1)의 순서로 계산해 주었다.

그럼 나머지 행들은 더 해보지는 말고, 이 부분을 코드로 구현하는 부분을 한번 알아보자.

DP[1][1] = MAP[1][1];
for (int i = 1; i <= M; i++) DP[1][i] = DP[1][i - 1] + MAP[1][i];
for (int i = 2; i <= N; i++)
{
    for (int j = 1; j <= M; j++)
    {
        Temp[i][j][0] = DP[i - 1][j] + MAP[i][j];
        Temp[i][j][1] = DP[i - 1][j] + MAP[i][j];
    }
    for (int j = 2; j <= M; j++) Temp[i][j][0] = Max(Temp[i][j][0], Temp[i][j - 1][0] + MAP[i][j]);
    for (int j = M - 1; j >= 1; j--) Temp[i][j][1] = Max(Temp[i][j][1], Temp[i][j + 1][1] + MAP[i][j]);
    for (int j = 1; j <= M; j++) DP[i][j] = Max(Temp[i][j][0], Temp[i][j][1]);
}

본인이 구현한 코드이다. 위의 코드에서 DP[][] 가 이 글에서 F[][]의 역할을 하는 친구이다.

line1)은 Case1에 속하는 구문이다. 바로 (1 , 1)에서 얻을 수 있는 최대가치를 계산한 부분이다.

line2)는 Case2에 속하는 구문이다. 예외적으로 첫 번째 행에 대해서만 따로 계산을 해 주었다.

line3 ~ 13)이 본격적으로 시작되는 Case3에 속하는 구문이다.

먼저, line5 ~ 8)을 보게 되면, 새로운 변수 Temp[][][] 가 등장하는데, 이 변수가 의미하는 것은 다음과 같다.

Temp[a][b][0] = C : (a , b)로 오른쪽으로 들어왔을 때, 얻을 수 있는 가치는 C원입니다. 를 의미한다.

즉, (a , b - 1)에서 오른쪽으로 움직여서 (a , b)로 왔을 때 얻을 수 있는 가치를 저장하는 변수이다.

Temp[a][b][1] = C : (a , b)로 왼쪽으로 들어왔을 때, 얻을 수 있는 가치는 C원입니다. 를 의미한다.

즉, (a , b + 1)에서 왼쪽으로 움직여서 (a , b)로 왔을 때 얻을 수 있는 가치를 저장하는 변수이다.

그리고 최종적으로 보게되면 line12)에서는 DP[][]배열에, 2개의 값 중 더 큰 값을 저장하는 과정이 있다.

이 부분은 조금만 아래쪽에서 이야기를 해보고, 먼저 코드에 전체적인 이야기를 계속 이어가보자.

line5 ~ 8)에서 보게되면, Temp변수에 임시로 값을 저장해주는 부분이다. 바로, "가장 우선적으로 계산할 수 있는" 위에서 아래쪽으로 내려오는 경우를 저장해 주고 있는 구문이다.

line 10)은 왼쪽에서 오른쪽으로 움직이는 경우, 얻을 수 있는 가치를 갱신하면서 저장해주는 구문이다.

왼쪾에서 오른쪽으로 움직이는 경우에는, (2 , 1)은 계산을 하지 못했듯, 1열에 대해서는 계산이 불가능하다. 따라서 for문을 보게 되면, 2열부터 M열까지 반복하는 것을 확인할 수 있다.

line 11)은 오른쪽에서 왼쪽으로 움직이는 경우, 얻을 수 있는 가치를 갱신하면서 저장해주는 구문이다.

오른쪽에서 왼쪽으로 움직이는 경우에는, (2 , 5)는 계산을 하지 못했듯, M번째 열에 대해서는 계산이 불가능하다. 따라서 for문을 보게되면, M - 1열부터 1열까지 반복하는 것을 확인할 수 있다. 또한 ! 역순으로 계산하기 위해서 1 ~ M - 1의 순서가 아닌,

M - 1 ~ 1의 순서로 계산을 진행해주고 있다.

line12)에서 최종적으로 F[][] 배열에 값을 최대가치로 설정해주고 있는 부분이다.

그럼 여기서 Temp 변수에 대해서 이야기를 좀 해보자.

#Q) Temp가 갑자기 왜 필요한 걸까 ?? 따로 저장하고 옮길바에 ,바로바로 갱신하면서 저장을 해버리면 안될까 ??

- Temp가 필요한 이유는 바로 문제에서 제시한 "한 번 탐색한 지역은 탐사하지 않는다" 라는 조건 때문이다.

  Temp는 임시저장용 변수이다. 위에서도 말했듯이, 왼쪽에서 들어오는 경우, 오른쪽에서 들어오는 경우를 나눠서

  각각 따로따로 저장 후, 최종적으로 다시 비교를 해서 각 좌표의 최대 가치를 갱신하게 된다.

  그럼 ! 아래와 같이 코드를 구현했다고 가정해보자.

DP[1][1] = MAP[1][1];
for (int i = 1; i <= M; i++) DP[1][i] = DP[1][i - 1] + MAP[1][i];
for (int i = 2; i <= N; i++)
{
    for (int j = 1; j <= M; j++) DP[i][j] = DP[i - 1][j] + MAP[i][j];
    for (int j = 2; j <= M; j++) DP[i][j] = Max(DP[i][j], DP[i][j - 1] + MAP[i][j]);
    for (int j = M - 1; j >= 1; j--) DP[i][j] = Max(DP[i][j], DP[i][j + 1] + MAP[i][j]);
}

   크게 달라진 것은 없다. line5)가 위에서는, Temp 라는 변수에 "가장 우선적으로 계산했을 때의 가치를 저장" 했었지만,

   위의 코드에서는 DP배열에 그대로 값을 설정해 주었다.

   line6 , 7) 또한 마찬가지이다. Temp변수를 비교하는 것이 아니라, DP배열 그대로를 비교하면서 저장해 주고 있다.

   그렇다면, 위와 같이 구현했을 때 발생할 수 있는 문제점이 무엇일까 ??

   예를 들어서 다음과 같은 상황을 가정해 보겠다.

.

  2행에 대한 계산을 진행할 때, 가장 우선적으로 위에서 내려오는 경우를 계산하였고, 2차적으로 왼쪽에서 오른쪽으로

  움직이는 경우를 계산했을 때, (2 , 5)가 가질 수 있는 최대 가치가 위에 그림으로 표시해놓은 주황색 경로를 따라 왔을 때

  최대가치를 얻었다고 가정해보자.

  그리고 나서, 마지막으로 오른쪽에서 왼쪽으로 움직이는 경우를 계산했을 때, (2 , 4)가 가질 수 있는 최대 가치를 생각해보자.

  먼저, 기존에 구해놓은 (2 , 4)에서의 최대가치가 'K' 라고 가정하겠다.

  그런데, 오른쪽에서, 즉, (2 , 5)에서 왼쪽으로 움직임으로써 (2 , 4)에 도달하는 경로를 확인해보니, 그 가치가 K보다 더

  큰 상황인 것이다. 그럼 (2 , 4)의 가치를 갱신할 수 있을까 ??

  갱신할 수가 없다. 왜 ?? (2 , 5)가 가지고 있는 가치는 이미 (2 , 4)를 지나왔기 때문에, 이 떄 (2 , 4)의 가치를

 갱신해 버리면 문제에서 제시한 "한번 탐사한 지역은 탐사하지 않는다." 라는 조건에 위배되어버리기 떄문이다.

  즉 ! 갱신을 할 수가 없다.

  따라서 우리는, "상대적으로 오른쪽에 있는 좌표 (x , y + 1)에서 왼쪽으로 움직여서 (x , y)로 올 때의 가치를 계산할 때,

  (x , y + 1)은 기존에 (x , y)를 방문한 적이 없어야 한다" 라는 조건을 챙겨주어야 한다.

  이 부분 때문에 Temp변수를 사용한 것이다.

  가장 처음에 Temp[][][0] 에 위쪽에서 내려오는 경우 얻을 수 있는 가치를, Temp[][][1]에도 위쪽에서 내려오는 경우

  얻을 수 있는 가치를 저장해 두었다. 그리고 왼쪽에서 오른쪽으로 움직이는 경우 Temp[][][0]의 값을 통해 계산을 하고

  가치를 갱신해 주었고, 오른쪽에서 왼쪽으로 움직이는 경우 Temp[][][1]의 값을 통해 계산을 하고 가치를 갱신해 주었다.

  즉 ! Temp변수를 만들어서 서로 독립적으로 계산을 해버리기 때문에, "절대로 좌표를 중복적으로 탐색하는 경우"를 없애버린

  것이다.

  그리고 최종적으로 다시 DP[][]배열에 해당 좌표에 얻을 수 있는 최대 가치를 갱신해 주었다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int DP[MAX][MAX];
int Temp[MAX][MAX][3];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    DP[1][1] = MAP[1][1];
    for (int i = 1; i <= M; i++) DP[1][i] = DP[1][i - 1] + MAP[1][i];
    for (int i = 2; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            Temp[i][j][0] = DP[i - 1][j] + MAP[i][j];
            Temp[i][j][1] = DP[i - 1][j] + MAP[i][j];
        }
        for (int j = 2; j <= M; j++) Temp[i][j][0] = Max(Temp[i][j][0], Temp[i][j - 1][0] + MAP[i][j]);
        for (int j = M - 1; j >= 1; j--) Temp[i][j][1] = Max(Temp[i][j][1], Temp[i][j + 1][1] + MAP[i][j]);
        for (int j = 1; j <= M; j++) DP[i][j] = Max(Temp[i][j][0], Temp[i][j][1]);
    }
    cout << DP[N][M] << 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;
}