[Programmers] 경주로 건설

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

방향을  꺾는 것을 확인한다는 점에서 리틀 프렌즈 사천성 문제와 비슷한 문제였습니다.

https://jaimemin.tistory.com/2147

[Programmers] 리틀 프렌즈 사천성

 

{0, 0}에서 {N - 1, N - 1}까지 가는 경로가 무조건 존재하고 도로를 설치하는 최소 가격을 구해야 하므로 우선순위 큐를 이용한 BFS 알고리즘이라는 점은 자명합니다.

여기서 한 단계 더 나아가 인접한 두 칸에 도로를 설치했을 때 최소 누적 금액도 트래킹 해야 하므로 visited 배열을 선언했습니다.

 

알고리즘은 아래와 같습니다.

1. 좌표, 누적 금액, 그리고 이전 방향을 저장하는 State 구조체를 선언하고 해당 구조체 타입의 우선순위 큐를 선언해줍니다. (우선순위는 누적 금액이 낮은 순서)

2. 인접한 두 칸 사이의 최소 비용을 트래킹하기 위해 visited 배열을 선언해주고 모두 INF로 초기화해줍니다.

2.1 board는 최대 25 * 25이므로 좌표를 (25 * y + x)와 같은 형태로 압축 가능

2.2 사실 25 * 25 * 25 * 25 4차원 배열보다 위와 같이 2차원 배열로 선언하는 것이 메모리를 조금 더 사용하지만 개발 편의성을 위해 2차원 배열로 선언했습니다.

3. {0, 0}부터 BFS를 진행하여 최초로 {N - 1, N - 1}에 도달하는 State의 cost를 반환해줍니다.

3.1 코너를 돌 때 500원 그리고 직진을 할 때 100원이 소모되므로 코너를 돌았을 경우 누적 금액에서 500원이 아닌 600원을 더해줘야 합니다.

3.2 모든 경우의 수를 확인하면 TLE가 발생하므로 가지치기를 해야 합니다. visited[현재 좌표][다음 좌표] 값이 현재 누적 금액보다 높거나 같을 경우에만 BFS를 계속 진행합니다.

3.3 출발점에서는 이전 방향을 -1로 두어 코너를 도는 여부를 체크하지 않습니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~