2169. 로봇 조종하기

코로나19의 빠른 종식을 기원합니다.

2169번: 로봇 조종하기

---

지형을 탐사하며, 탐사 가치를 최대로 해야 하는 문제이다. 이때 로봇은 오른쪽, 왼쪽, 아래로만 움직일 수 있으며, 한 번 방문한 지역은 다시 방문할 수 없다.

 

전형적인 완전 탐색 문제이다. 그러나 완전 탐색으로는 최대 O(3^(N+M))을 감당할 수 없으므로 동적 계획법(이하 dp)을 활용해야 한다.

 

관찰

1. 로봇은 위쪽으로 움직일 수 없다. 따라서 지형의 마지막 행에 도착한 로봇은 반드시 오른쪽으로만 이동해야 한다. 왼쪽으로 움직였을 때 (N, M)에 도달할 수 있는 방법이 없기 때문이다.
2. 예를 들어, (r-1, c)에서 (r, c)로 이동한 로봇은 왼쪽으로는 이동할 수 없다. 이러한 중복 방문을 방지하기 위해 로봇이 어느 방향에서 왔는지 알려주는 from 매개변수를 정의하자. from의 값은 왼쪽에서 왔다면 0, 오른쪽에서 왔다면 1, 위에서 왔다면 2이다.
3. 배열의 값이 음수로 주어질 수 있다. dp 테이블을 0 또는 -1로 초기화하면 안 된다.

동적 계획법에 익숙하다면 위의 힌트만으로 문제를 풀 수 있을 것이다. 어렵다면 다음 글을 계속 읽어 보자.

# 자세한 풀이

1번에 의하여 마지막 줄의 dp 테이블을 채울 수 있다. 

dp[n][m][0] = dp[n][m][2] = value[n][m]
for j from m to 1:
    dp[n][j][2] = dp[n][j][0] = dp[n][j + 1][2]

이제 (1, 1)에서 출발하여 완전 탐색을 수행하자. 이때 2번을 잊으면 안 된다. 로봇이 어느 방향에서 왔는지에 따라 로봇의 탐색 방향을 제한해야 한다.

---

온라인 개강 덕분에 여유 시간이 많아져서.. 요즘엔 종만북을 보고 있다. 지금 9장 동적 계획법 테크닉을 보고 있는데, 책이 정말 좋다. 알고리즘에 흥미가 있는 사람이라면 꼭 읽어야 한다고 생각한다. 광고 아닙니다. 진심입니다.