[프로그래머스] 경주로 건설 (파이썬)

난이도 : LV3

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

문제 해결 아이디어

• 코너 생성여부를 어떻게 판단 할것인가
  • q에 x좌표 y 좌표 뿐만 아니라 어떤 방향으로 이동했는지 나타내는 direction 도 포함시킨다
  • dx, dy 값이랑 비교해서 같은 방향일 경우 +100, 다른방향일 경우 +600
• 각 좌표별 cost 값을 2차원 배열에 담을 것인가 3차원 배열에 담을 것인가
  • 처음에 2차원 배열을 통해 문제를 풀었었는 데 테스트케이스 마지막 번호가 통과 되지않았다.
  • 반례를 찾아보니 2차원 bfs 에서는 다음 q에 들어갈 nx, ny 가 같거나 작은 cost를 가질 경우에만 q에 추가를 했는데 이러면 nx,ny 에서 다음 지점이 코너인 경우와 직선인 경우 더 낮은 cost가 다음 지점에서는 더 높은 cost가 되는 경우가 생겼다.
  • 3차원 배열을 통해 같은 방향에서 온 cost 끼리 대소비교를 통해 visitd[i][nx][ny] 에 cost를 저장함으로써 해결했다.
• 기존 BFS 문제와는 달리 더 낮은 cost를 가진다면 재방문이 가능하다.

소스코드

from collections import deque
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def bfs(x,y,direction,cost,board):
    n = len(board)
    q = deque()
    q.append((x,y,direction,cost))
    INF = int(1e9)
    visited = [[[INF] * n for _ in range(n)] for _ in range(4)] 
    
    while q:        
        x,y,direction,cost = q.popleft()        
        
        if x == n-1 and y == n-1:
            continue
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0: 
                if direction == -1:
                    new_cost = cost + 100
                elif direction % 2 == i % 2:
                    new_cost = cost + 100
                else:
                    new_cost = cost + 600
                        
                if new_cost < visited[i][nx][ny]:
                    q.append((nx,ny,i,new_cost))
                    visited[i][nx][ny] = new_cost
    minVal = INF
    
    for i in range(4):
        minVal = min(minVal, visited[i][-1][-1])
    return minVal

def solution(board):
    return bfs(0,0,-1,0,board)