경주로 건설 (67259번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 경주로 건설 (67259번)

 

난이도 : Lv 3

알고리즘&자료구조 : BFS (너비 우선 탐색)

풀이 소요 시간 : 40 mins

 

 

import sys
INF = sys.maxsize


def solution(board):
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]
    n = len(board)
    memo = [[[INF]*4 for _ in range(n)] for _ in range(n)]
    memo[0][0][0] = memo[0][0][2] = 0
    q = [(0, 0, 0, 0), (0, 0, 0, 2)]
    while q:
        tmp = []
        for r, c, cost, d in q:
            nr, nc = r+dr[d], c+dc[d]
            ncost = cost+100
            if 0 <= nr < n and 0 <= nc < n and not board[nr][nc] and ncost < memo[nr][nc][d]:
                memo[nr][nc][d] = ncost
                tmp.append((nr, nc, ncost, d))
            for i in range(4):
                if i==d:
                    continue
                nr, nc = r+dr[i], c+dc[i]
                ncost = cost + 600
                if 0 <= nr < n and 0 <= nc < n and not board[nr][nc]  and ncost < memo[nr][nc][i]:
                    memo[nr][nc][i] = ncost
                    tmp.append((nr, nc, ncost, i))
        q = tmp
    return min(memo[-1][-1])

 

 

2020 카카오 인턴십 기출문제이다.

BFS 를 응용해서 풀 수 있었다.

 

---

 

일반적인 BFS와 다른 점은,

각 좌표마다 4개의 최솟값을 갖고 있다는 점이다.

 

예를 들어, (2, 3) 좌표가 있다고 하면,

① 동 : (2, 2) → (2, 3)
② 서 : (2, 4) → (2, 3)
③ 남 : (1, 3) → (2, 3)
④ 북 : (3, 3) → (2, 3)

이렇게 4가지 경우가 있을 수 있다.

 

각 좌표마다, 위의 각 4가지 방향에 대해 각각 최솟값을 저장하고 있어야 한다.

이를 저장할 (n, n, 4) 크기의 리스트 memo 를 만든다.

 

---

 

큐 (Queue) 의 각 원소는 (행 좌표, 열 좌표, 현재까지 비용, 방향) 으로 구성했다.

 

제일 처음에 (0, 0) 에서 출발하는데,

(0, 0) 에서는 "남" 및 "동" 방향으로만 이동할 수 있으므로,

초기 Queue 는 [(0, 0, 0, 0), (0, 0, 0, 2)] 로 설정했다.

 

이후 BFS 를 진행하면서,

기존 방향과 동일한 방향으로 이동할 때는 100을,

그리고 기존 방향과 다른 방향으로 이동할 때는 600 (=100+500)을 더해주면서,

Queue 를 업데이트 해 나간다.

 

위 과정을 Queue 가 비워질 때까지 진행한다.

 

---

 

BFS 작업이 마무리되면, memo 의 (n-1, n-1) 좌표값 4개 중 최솟값을 반환한다.