경주로 건설 [2020 카카오 인턴십]

1) 문제 접근 방법

- 이 문제는 일반적인 BFS와는 다르게, 최소값 정보를 Map에 저장해 놓은 다음에,

  Map에 저장해 놓은 값보다 작을 때만, 값을 업데이트하는 식으로 BFS 탐색을 진행한다.

  이 때, 다음 방향이 현재 방향과 같으면 nCost = cost+100을,

  다음 방향이 현재 방향과 다르면 nCost = cost+600을 하는 식으로 진행한다.  

  이를 위해서는 dir과 cost 정보를 q에 저장해서 전달해야 한다. 

 

- 최소값과 관련된 것이므로, BFS를 사용하는 편이 좋다. 

- >파이썬에서 언제 DFS를 사용해도 되고, 언제 BFS를 사용하는 것이 좋은지 숙지하는 것이 필요하다. 

 

- bfs(board, 1), bfs(board,2)로 두 방향에 대해서 bfs를 돌려주고, 그 중에서 min값을 답으로 본다는 접근도 중요하다

-> 또한, bfs 메소드로 결과값을 리턴한다는 발상도 중요하다.  

 

 

2) 소스 코드

from collections import deque 

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
minCost = int(1e9)


def bfs(board, dir):
    
    N = len(board)
    
    costMap = [[int(1e9)]*N for _ in range(N)]
    
    q = deque()
    
    q.append([0, 0, 0, dir])
    
    
    while q:
        
        x, y, cost, dir = 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 and nx<N and 0<=ny and ny<N and board[nx][ny] == 0:
                
                if dir == i:
                    nCost = cost+100
                else:
                    nCost = cost+600
                
                
                if nCost < costMap[nx][ny]:
                    costMap[nx][ny] = nCost
                    q.append([nx, ny, nCost, i])
                
          
    
    return costMap[N-1][N-1]      
    

    
    
    
def solution(board):
    answer = 0
    
    N = len(board)
    minCost = min(bfs(board, 1), bfs(board, 2))
    
    answer = minCost
    
    return answer