[프로그래머스][level3] 경주로 건설 -python/ bfs

문제 링크

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

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

 

풀이 

• bfs 풀이했는데, 테스트 케이스 25번에서 계속 실패 하였다. 

# 실패한 코드 
from collections import deque 

# 아래, 위, 오른쪽, 왼쪽 
dx = [1,-1,0,0]
dy = [0,0,1,-1]
INF = int(1e9)
def bfs(x,y,n,board):
    q = deque()
    
    # 위치, 방향, 비용 
    # 처음 위치에서는 아래로 이동 또는 오른쪽으로 이동 
    q.append((x,y,0,0))
    q.append((x,y,2,0))
    
    # 비용 저장할 테이블 
    cost = [[INF]*n for _ in range(n)]
    # 출발 위치 비용 초기화 
    cost[x][y] = 0 
    
    while q :
        x, y, d, c = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            new_cost = 0 
            
            # 같은 방향으로 직진 시 
            if d == i :
                new_cost = c + 100
            # 커브 시에는 직선 도로 + 코너 
            else:
                new_cost = c + 600
            
            # 범위에 속하고, 벽이 아니고 더 최소 비용으로 이동할 수 있으면 
            if 0<= nx < n and 0 <= ny < n and board[nx][ny] != 1 and cost[nx][ny] > new_cost:
                # 갱신 
                cost[nx][ny] = new_cost 
                # 큐에 추가 
                q.append((nx,ny,i,new_cost))
                    
    #print(cost)
    return cost[n-1][n-1]
    
def solution(board):
    
    return bfs(0,0,len(board), board)

첫 출발점에서 오른쪽으로 갔을 때랑 아래쪽으로 갔을 때를 각각 나누어서 최솟값을 구하니깐 통과하였다. 

from collections import deque 

# 아래, 위, 오른쪽, 왼쪽 
dx = [1,-1,0,0]
dy = [0,0,1,-1]
INF = int(1e9)

def bfs(x,y,n,d, board):
    q = deque()
    
    # 위치, 방향, 비용 
    q.append((x,y,d,0))
    # 비용 저장할 테이블 
    cost = [[INF]*n for _ in range(n)]
    # 출발 위치 비용 초기화 
    cost[x][y] = 0 
    
    while q :
        x, y, d, c = q.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            new_cost = 0 
            # 직진 시 직진 도로 비용 100 
            if d == i :
                new_cost = c + 100
            # 커브 시 비용 직진 도로 100 + 코너 500 
            else:
                new_cost = c + 600
            
            # 범위에 속하고, 벽이 아니고, 더 최소비용으로 이동할 수 있을 때 
            if 0<= nx < n and 0 <= ny < n and board[nx][ny] != 1 and cost[nx][ny] >= new_cost:
                # 최소 비용 갱신 
                cost[nx][ny] = new_cost 
                # 큐에 추가 
                q.append((nx,ny,i,new_cost))
                    
    return cost[n-1][n-1]
    
def solution(board):
    result = 0 
    # 첫 출발점에서 아래로 이동했을 때와 오른쪽으로 이동했을 때 최솟값 
    result = min(bfs(0,0,len(board),0, board), bfs(0,0,len(board),2, board))
    
    return result