읽기 전
- 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
- 개인적으로 배운 점을 정리한 글입니다.
문제 링크
Programmers. 경주로 건설
문제 풀이
특정 지점에 도달할 때 비용이 최소로 들어야 한다는 점에서 다익스트라 알고리즘을 사용해야 한다는 점은 알아채고 적용했으나 테스트케이스 단 하나를 통과하지 못했다. 라이트업을 참고하니 특정 칸에서 어떤 경로가 더 비용이 적더라도 그 경로가 마지막 칸까지의 비용이 최소인 경로임은 보장하지 않는다는 점이다. 즉, 더 비싸더라도 다른 방향에서 접근한 경로가 마지막에서 더 저렴할 수 있다는 의미이다. 따라서, 다익스트라를 사용하되 접근할 수 있는 4개의 방향에 대한 비용을 체크하고 마지막 칸에 대해 비용 배열의 최솟값을 리턴해야 한다.
- 모든 칸에 대해 4가지 방향으로 접근한 경로의 비용을 저장할 3차원 방문 배열 정의
- 초항은 0,0에서 출발해 오른쪽과 아래쪽으로 진행이 가능하기에 board상태 체크하고 비용 업데이트 후 큐에 넣는다,
- 다익스트라를 진행하는 동안 가고자하는 노드의 현재 방향에 대한 기록된 비용보다 크다면 skip하고 그렇지 않으면 갱신한 뒤 4가지 방향에 대해 범위 체크, 방향이 다르면 커브를 의미하므로 500을 더해준다.
- 큐가 모두 비워질 때까지 탐색한 후 마지막 칸이 갖는 비용의 최솟값 리턴
python 코드
| from collections import deque |
| def solution(board): |
| N = len(board) |
| INF = float('inf') |
| visited = [[[INF] * 4 for _ in range(N)] for _ in range(N)] |
| dr = [0, 0, 1, -1] |
| dc = [1, -1, 0, 0] |
| q = [] |
| if board[1][0] == 0: |
| visited[1][0][2] = 100 |
| q.append((100, 1, 0, 2)) |
| if board[0][1] == 0: |
| visited[0][1][0] = 100 |
| q.append((100, 0, 1, 0)) |
| visited[0][0] = [0,0,0,0] |
| q = deque(q) |
| while q: |
| cost, r, c, d = q.popleft() |
| if visited[r][c][d] >= cost: |
| visited[r][c][d] = cost |
| else: |
| continue |
| for i in range(4): |
| nd = int(i) |
| nr, nc = r + dr[nd], c + dc[nd] |
| if 0 > nr or nr >= N or 0 > nc or nc >= N: |
| continue |
| ncost = cost + 100 |
| if d != nd: |
| ncost += + 500 |
| if visited[nr][nc][nd] < ncost or board[nr][nc] == 1: |
| continue |
| visited[nr][nc][nd] = ncost |
| q.append((ncost, nr, nc, nd)) |
| return min(visited[-1][-1]) |