출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 경주로 건설
새로 알게된 것들
다이나믹 프로그래밍 알고리즘에 대해 완전 잘못 알고 있었던 것 같다. DP는 지금까지 한번 탐색을 했던 경우라면 다음엔 이 경우에 왔을 때 다시 탐색하는 것이 아니라 이미 탐색한 값을 반환하는 것으로 알고 있었다. 하지만 한번 탐색을 했을 때 그 경우가 과면 독립적인 경우인지 확인해봐야 할 것 같다. 만약 독립적이지 않고 종속적인 경우라면 한번의 탐색으로 그 경우에 완전한 탐색값을 얻을 수 없기 때문에 다음에 그 경우에 도착하더라도 이미 탐색한 경우라 바로 반환하는 것이 아닌 다시 탐색을 해보고 더 정확한 값이 나오면 이미 탐색한 값을 업데이트 해줘야 한다. 예시로 플로이드 와샬 알고리즘도 DP를 활용했는데 이전에 초기화가 된 적이 있더라도 이전보다 더 작은 거리일 경우에는 업데이트를 해준다.
풀이
깊이우선탐색과 너비우선탐색 모두 사용해도 답을 구할 수 있다. 두 탐색을 모두 다익스트라 알고리즘에 기반하여 구현해야 한다.
1. 도로의 현재 방향이 어디를 가리키냐에 따라 값이 다르게 나올 수 있기 때문에 한 격자에 4가지의 방향을 가지기 때문에 N X N X 4 크기의 리스트를 초기화해준다.
2. 큐에 처음 (0, 0) 에서 아래로 가는 방향과 오른쪽으로 가는 방향에 대한 정보를 넣어둔다.
3. 다익스트라 알고리즘을 통해 시작점에서 모든점까지의 최소비용을 구한다.
4. 마지막 (n - 1, n - 1) 의 값을 확인한다.
코드
def solution(board):
INF = 987654321
n = len(board)
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
costMap = [[[INF, INF, INF, INF] for _ in range(n)] for _ in range(n)]
costMap[0][0] = [0, 0, 0, 0]
queue = [[0, 0, 0], [0, 0, 1], ]
while queue:
x, y, d = queue.pop(0)
for i in range(4):
nextX, nextY = x + dx[i], y + dy[i]
if 0 <= nextX < n and 0 <= nextY < n and board[nextX][nextY] == 0:
cost = costMap[x][y][d] + 100 if d == i else costMap[x][y][d] + 600
if cost < costMap[nextX][nextY][i]:
costMap[nextX][nextY][i] = cost
queue.append([nextX, nextY, i])
answer = min(costMap[n - 1][n - 1])
return answer다른 사람 풀이를 보며 알게 된 점
엄청 어렵게 생각했지만 다른 사람들의 풀이를 보고 문제가 이렇게 추상화될 수 있다는 것을 알게되었다. 지금은 실력이 부족하여 문제를 쉽게 보지는 못하겠지만 계속 쉽게 보는 연습을 해야겠다.
느낀점
DP에 대한 잘못된 개념으로 인해 너무 많은 시간을 쏟았다. DP에 대해 너무 좁은 의미로만 알고 넓은 의미를 알지 못해 문제를 아예 잘못된 방향으로 이끌려가서 아쉽다.
