[프로그래머스] 경주로 건설

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

초기에 DFS 를 재귀로 탐색하여 모든 경우를 탐색을 시도하였으나, 시간초과로 통과하지 못하였습니다.

그래서 BFS 탐색을 하며 DP를 이용하는 방식으로 접근하였습니다.

2) 알고리즘

• BFS
• DP

3) 풀이 코드

사용 언어 - Python

from collections import deque

def solution(board):
    dr = [-1, 0, 1, 0]                      # 상 우 하 좌
    dc = [0, 1, 0, -1]
    N = len(board)                          # 보드판의 길이
    cost = [[1e10] * N for _ in range(N)]   # 각 좌표로 이동하는데 발생하는 비용

    def BFS():
        q = deque([(0, 0, 0, -1)])          # 행 열 좌표, 해당 좌표로 오는데 발생한 비용, 이전에 진행하던 방향
        cost[0][0] = 0                      # 시작 좌표는 비용이 없음

        while q:
            y, x, price, d = q.popleft()
            
            for k in range(4):              # 4 방향 모두 탐색
                r = y + dr[k]
                c = x + dc[k]

                if 0 <= r < N and 0 <= c < N and board[r][c] != 1:          # 범위내이고 벽이 아니라면
                    if (d == -1 or d == k) and price + 100 <= cost[r][c]:   # 초기 시작이거나 방향이 같을때, 다음 좌표가 100 비용이 늘어나더라도, 지금의 경우가 더 낮은 비용일떄
                        cost[r][c] = price + 100
                        q.append((r, c, price + 100, k))                    
                    elif price + 600 <= cost[r][c] + 200:                   # 방향이 다르고, 추가적인 비용이 400 이하로 차이가 날때 (예외 상황)
                        cost[r][c] = price + 600
                        q.append((r, c, price + 600, k))

    BFS()

    return cost[N-1][N-1]       # 도착지점 비용 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

초기에 비용에 관련된 부분을 기록하였고, 그것보다 낮은 비용이 발생시에만 새로 갱신하였습니다.

그러나 특정 상황 어떠한 좌표에서 더 높았던 비용의 루트가 최종적으로 더 낮아지는 비용의 루트가 발생하게 되는 상황이 발견되었습니다.

(ex.

1번 루트 - 직진(1, 3, 100) => 직각(1, 3, 200) => 직진(2, 3, 800) => 직진(3, 3, 900),

2번 루트 - 직진(2, 2, 500) => 직각(2, 3, 600) => 직진(3, 3, 1200) 위의 두가지 루트는 2,3 에서 2번 루트가 더 낮은 가격이지만, 결과적으로 3, 3에 도착하였을때는 1번 루트가 더 낮은 가격이 되어서, 1번루트를 선택하여야 합니다.)

 

이러한 예외 상황을 발견하고, 해결하는데 오래 걸렸습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다