[프로그래머스][KAKAO_인턴][2020] 경주로 건설

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import defaultdict, deque
import sys

def solution(board):
    answer = sys.maxsize
    N = len(board)
    memo = defaultdict(lambda: sys.maxsize)
    dir = [(0,1),(1,0),(-1,0),(0,-1)]
    q = deque([(0, 0, (-1, -1), 0, 1)])
    while q:
        i, j, before, cost, chance = q.popleft()
        if i == N-1 and j == N-1:
            answer = min(answer, cost)
            continue

        for d_i, d_j in dir:
            nw_i = i+d_i
            nw_j = j+d_j
            if 0 <= nw_i < N and 0 <= nw_j < N and board[nw_i][nw_j] != 1:
                if before == (d_i, d_j) or (i == 0 and j == 0):
                    crnt_cost = cost + 100
                else:
                    crnt_cost = cost + 600

                if crnt_cost < answer and crnt_cost <= memo[(nw_i, nw_j)]:
                    memo[(nw_i, nw_j)] = crnt_cost
                    q.append((nw_i, nw_j, (d_i, d_j), crnt_cost, chance))
                elif crnt_cost < answer and chance > 0:
                    q.append((nw_i, nw_j, (d_i, d_j), crnt_cost, chance-1))

    return answer

• 좌표
  • 최소 비용을 찾는 BFS
  • prunning을 위해 해당 좌표에 도달했던 cost보다 크면 탐색하지 않음
  • 그러나 위 prunning 조건의 한계로 인해 기회를 1회 부여함
    - 특정 좌표에 도달할 때, cost가 더 작은 경우가 존재했다
    - 그러나 코너로 인해 해당 좌표 이 후 cost가 역전되는 상황이 벌어졌다
    - 프로그래머스 질문하기 참조

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 설마하던 일이 일어났다
  
  • cost 기준으로 탐색 수를 줄이면서 설마 cost가 역전될까 고민을 했다
  • 아무리 생각해도 그럴 일은 없을 것 같았는데, 프로그래머스 질문하기에 올려진 예제를 보며 가능하다는 것을 깨달았다
• 통과한 코드가 옳은 방법인지 모르겠다
  • cost가 역전되는 순간은 단 한 번이라고 생각한다
    - 두 가지 길이 한 좌표에서 마주칠 때
    - 두 길 중 하나는 먼 길을 돌아와 cost가 크고 직진인 경우
    - 두 길 중 다른 하나는 가까운 길로 cost가 적고 코너인 경우
  • 또 이러한 경우가 발생하는 이유는 출발점의 cost가 같기 때문이라고 생각한다
    - 처음 출발시 우측, 아래 두 방향으로 출발할 수 있다
    - 이 때 두 방법 모두 직진으로 판단되어 cost가 같다
    - 따라서 cost 역전이 발생할 수 있는 경우는 단 한 번이 아닐까 싶다
  • 그럼에도 반례가 있을 지 모르겠다