경주로 건설

문제

---

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

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

 

나의 풀이

---

최단 경로를 찾는 BFS와 DP가 합쳐진 유형의 문제이다. 처음엔 DFS로 풀어보려 했으나 시간초과에 걸렸다. 대부분은 BFS로 푸는 것이 좋은 경우가 많다. 시간 초과 외에도 재귀의 최대 깊이에 걸려 DFS로 작성한 답안에서 RUNTIMEERROR가 나는 경우도 많기 때문이다.

본 문제의 경우 단순히 탐색만 하는 것이 아니라 방향성에 대한 정보도 같이 queue에 저장해주어야 한다. 코너와 직선 도로의 cost가 다르기 때문이다.

1. 출발점 (0,0)부터 탐색을 하며 q에 방문한 지점을 삽입한다.
2. 이 때, 정보는 (방문지점의 x좌표, 방문지점의 y좌표, 해당 지점까지 도달하는데 드는 cost, 방향)으로 저장한다.
3. 나의 경우 방향은 (0,1,2,3) == (우,좌,하,상)으로 설정하였다.
4. 이제 아래 부분의 코드가 중요한데, nx,ny를 갱신하면서 ncost도 같이 갱신해주어야 한다. 이 때, 선택지는 현재 지점에서 상,하,좌,우로 가는 4가지가 있다. 저장해둔 방향성 정보와 비교해 코너가 생성되면 600원을, 아니면 100원을 더해준다. 코너 생성 비용은 500원이지만 코너를 만들때에도 직선 경로가 하나 생성되어 결과적으로는 500+100인 600원을 더해주어야 한다.
5. 이 ncost가 기존에 저장되어있던 비용보다 작은 경우에만 갱신을 해주면 된다.
6. 여기서 드는 의문점은, i != direction 부분에서 기존에 왔던 방향과 반대 방향으로 돌아가는 경우는 코너가 아닌데도 600원을 더해주게 된다. 하지만 이것이 괜찮은 이유가 result[nx][ny] > ncost라는 조건에 의해 반대로 되돌아가는 경우 항상 기존의 cost보다 더 크게 되어 갱신이 안되고 지나치기 때문이다.

 

코드

---

from collections import deque
import math

dx,dy = [0,0,1,-1],[1,-1,0,0]

def solution(board):
    def bfs(startX,startY,startC,startD):
        n = len(board)
        result = [[math.inf for _ in range(n)] for _ in range(n)]
        q = deque()
        q.append((startX,startY,startC,startD))
        result[startX][startY] = 0
        while q:
            x,y,cost,direction = q.popleft()
            for i in range(4):
                nx,ny,ncost = x + dx[i], y + dy[i], cost+600 if i != direction else cost+100
                if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0 and result[nx][ny] > ncost:
                    result[nx][ny] = ncost
                    q.append((nx,ny,ncost,i))
        return result[-1][-1]
    return min(bfs(0,0,0,0),bfs(0,0,0,2))