백준 1149 RGB거리

백준 1149번

백준 1149 RGB거리 문제

그리디 알고리즘으로 해결할 수 있는 문제가 아니라는 것은 금방 눈치챌 수 있었다. 효율적으로 최솟값을 찾는 방법을 찾는 것이 이 문제의 의도라고 생각했다. 처음엔 DP를 활용해서 풀 생각을 하지 못했다. 집과 상관없이 최솟값을 탐색한 후에 연결이 되는지 확인하려고 했지만 매 loop에서 3n 크기의 리스트에서 최솟값을 탐색하는 건 너무 비효율적이라 포기했다.

DP를 활용한 풀이

모든 경우를 탐색해야 할 때는 꼭 DP를 활용한 풀이를 고려해봐야 한다. 이러한 경우 내가 고려해야 하는 것은

• 각 집 & 색마다 비용이 다르다
• 옆 집과 색이 달라야 한다

각 집과 색은 변수가 되어야 하고, 조건을 잊지 않고 리스트를 만들어 문제를 해결해야 한다. 변수는 2개이므로 2차원 배열을 활용한다.

어떠한 경우가 최선인지 현재는 알 수 없으므로 색을 칠하는 3가지 경우 모두 각각의 최솟값을 리스트에 저장

리스트 선언에서의 실수

내 첫 코드는 다음과 같다

import sys

numTestCases = int(sys.stdin.readline())
dpList = [list(map(int, sys.stdin.readline().split()))] + [[0, 0, 0]] * (numTestCases - 1)
for i in range(1, numTestCases):
    print(dpList)
    data = list(map(int, sys.stdin.readline().split()))
    dpList[i][0] = data[0] + min(dpList[i - 1][1], dpList[i - 1][2])
    print(dpList)
    dpList[i][1] = data[1] + min(dpList[i - 1][0], dpList[i - 1][2])
    print(dpList)
    dpList[i][2] = data[2] + min(dpList[i - 1][0], dpList[i - 1][1])
    print(dpList)

print(dpList)
print(min(dpList[numTestCases - 1]))

오류를 찾지 못했는데도 계속 답이 나오지 않았고 print문을 활용해 디버깅하는 과정에서 문제점을 찾게 되었다.

출력된 dpList를 보면 첫 인덱스를 제외하고는 모두 값이 똑같이 변한다는 것을 알 수 있다. dpList를 선언하는 과정에서 사용한 리스트의 곱셈은 하나의 리스트 주소를 공유한다는 것을 알 수 있었다. 즉 얕은 복사로 만들어진 리스트이기 때문에 이와 같은 오류가 발생했다. 이후에 오류를 수정하기 위해 append()를 활용해서 답을 얻어냈다.

2차원 이상의 배열에서 곱셈을 사용하는 것은 위험할 수 있다.
for문은 깊은 복사를 이용한다.

import sys

numTestCases = int(sys.stdin.readline())
dpList = [list(map(int, sys.stdin.readline().split()))] # 각 집으로 가는 동안 해당하는 RGB에서 최솟값을 저장하기 위한 DPList

for i in range(1, numTestCases):
    data = list(map(int, sys.stdin.readline().split()))
    data[0] += min(dpList[i - 1][1], dpList[i - 1][2])
    data[1] += min(dpList[i - 1][0], dpList[i - 1][2])
    data[2] += min(dpList[i - 1][0], dpList[i - 1][1])
    dpList.append(data)

print(min(dpList[numTestCases - 1]))