프로그래머스 <경주로 건설>

프로그래머스 <경주로 건설>

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

프로그래머스

---

경주로 건설

건설회사의 설계사인 죠르디는 최소 비용으로 자동차 경주로를 건설해야 한다.

경주로 부지는 N * N 크기의 정사각형 격자 형태이며 각 격자는 1 * 1 크기이다. 각 격자는 0 또는 1이 채워져있는데 1은 벽이기 때문에 경주로를 건설할 수 있다.

출발점인 (0, 0)에서 도착점인 (N-1, N-1) 까지 무사히 도달할 수 있도록 중간에 끊기지 않게 경주로를 건설해야 한다.

이때 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로는 직선 도로, 두 직선 도로가 서로 직각으로 만나는 지점을 코너라고 부른다. 직선 도로를 건설하는 비용은 100원이고 코너를 건설하는 비용은 500원이다.

죠르디를 위해 경주로를 건설하는데 필요한 최소 비용을 계산해주자.

---

문제해결

처음 문제를 봤을 때는 직선으로 가면 100원, 직각으로 가면 500원으로 계산해서 정답이 제대로 나오지 않았었다.

다시 확인해보니 직선 도로는 최소 거리만큼 지어야 하고 추가로 직각으로 만나는 경우에 코너를 지어야 한다는 것을 알 수 있었다. 하지만 그래도 정답이 제대로 나오지 않았다. 

그 이유는 방문체크를 잘못했기 때문이다.

처음 방문체크는 현재 위치까지의 건설 비용을 이용하여 이전에 해당 비용보다 적은 비용으로 온 적이 있다면 방문한 것으로 취급하였는데 이렇게 하면 문제는 다른 방향에서 같은 가격으로 올 때를 처리하지 못한다. 즉, (1, 1) 위치를 아래로 300원에 왔다면 (1, 1) 위치를 오른쪽으로 300원에 오는 경우를 고려하지 못한다.

 

따라서 방문체크 배열을 3차원 배열을 사용하였다.

visit[ i ][ j ][ k ] : k방향으로 (i, j)위치에 왔을 때 건설 비용의 최솟값

 

이렇게 고치고 나니 테스트케이스의 11번이 시간초과로 통과하지 못했고 테스트케이스의 19번이 9000ms 가 걸렸다.

 

BFS를 돌리는 자료구조로 deque를 사용하였는데 우선순위 큐인 heapq로 바꿔서 돌려주었다.

현재 문제는 (0, 0)에서 (N-1, N-1)까지 가는 것이기 때문에 큐에 들어가는 (i, j, 비용, 방향)이 순서대로 i, j, 거리, 방향으로 우선순위가 정해지기 때문에 비용이 작은 것부터 보며 로직이 진행되기 때문에 더 빨리 끝난다.

 

-> 테스트케이스 11번 3200ms, 테스트케이스 19번 1241ms

---

코드

import heapq
INF = 2e9
def solution(board):
    answer = INF
    N = len(board)
    # 상좌하우 -> 짝수는 상하, 홀수는 좌우
    di = [-1, 0, 1, 0]  
    dj = [0, -1, 0, 1]
    
    # Q, visit init
    Q = []
    # visit[i][j][k] = (i, j) 위치를 이전 방향을 k로 했을 때 건설한 비용의 최솟값
    visit = [[[INF for _ in range(4)] for _ in range(N)] for _ in range(N)]
    
    # add start
    heapq.heappush(Q, (0, 0, 0, -1)) # (i, j, 비용, 이전 방향)
    visit[0][0] = [0, 0, 0, 0]
    
    while Q:
        tp = heapq.heappop(Q)
        for k in range(4):
            ni = di[k] + tp[0]
            nj = dj[k] + tp[1]
            # 범위를 벗어나거나 벽인 경우 -> 경주로 건설 불가
            if ni < 0 or nj < 0 or ni >= N or nj >= N or board[ni][nj] == 1:
                continue
            # dist : 직선도로 한 개 건설 비용 추가
            dist = tp[2] + 100
            if isCorner(tp[3], k):  # 코너라면 코너 건설 비용 추가
                dist += 500
            # 방문 체크
            # 만약 visit 배열의 값이 dist보다 작다면 -> 이미 해당 경우로 왔었음
            if visit[ni][nj][k] < dist: 
                continue
            # 도착지에 도착했다면 answer update
            if ni == N-1 and nj == N-1:
                answer = min(answer, dist)
                continue
            # Q에 넣기
            heapq.heappush(Q, (ni, nj, dist, k))
            visit[ni][nj][k] = dist
    return answer
def isCorner(prev, now):   # dist : 거리, prev : 이전 방향, now : 현재 방향
    if prev == -1: # 처음 시작 -> 직선도로
        return False
    # 이전 방향, 현재 방향이 둘 다 짝수(상하)거나 둘 다 홀수(좌우) -> 직선도로
    if (now % 2 == 0 and prev % 2 == 0):
        return False
    if (now % 2 == 1 and prev % 2 == 1):
        return False
    # 코너
    return True

---

결과

---