[Python] 프로그래머스 - 경주로 건설

문제

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

프로그래머스

풀이

풀이 1

BFS 알고리즘을 기반으로 작성하되, 코너와 직선 도로의 경우를 구분하기 위해 방향에 대한 정보(d)를 queue에 추가적으로 넣어 구분.

이미 지난 길이라도, 더 적은 비용으로 갱신할 수 있는 경우에 갱신하도록 코드를 구현하였다.

def solution(board):
    from collections import deque
    d = ''
    n = len(board)
    answer = []
    q = deque([(0,0,d)])
    while q:
        x,y,d = q.popleft()
        for nx,ny in [(x-1,y),(x,y+1),(x+1,y),(x,y-1)]:
            if not (nx==0 and ny==0) and (0<=nx<n and 0<=ny<n) and board[nx][ny]!=1:
                if (d=='h' and x!=nx) or (d=='v' and y!=ny): # corner
                    nd = 'h' if d=='v' else 'v'
                    if board[nx][ny]==0:
                        board[nx][ny] = board[x][y]+600
                        q.append((nx,ny,nd))
                    elif board[nx][ny]>=board[x][y]+600:
                        board[nx][ny]=board[x][y]+600
                        q.append((nx,ny,nd))
                else: # straight
                    nd = 'h' if ny!=y else 'v'
                    if board[nx][ny]==0:
                        board[nx][ny] = board[x][y]+100
                        q.append((nx,ny,nd))
                    elif board[nx][ny]>=board[x][y]+100:
                        board[nx][ny] = board[x][y]+100
                        q.append((nx,ny,nd))

    answer = board[n-1][n-1]
                
    return answer

채점한 결과 몇개 케이스에서 오답으로 처리되었고, 조금 찾아보니 다음과 같은 테스트 케이스에서 오류가 발생하는 것을 알 수 있었다.

 

`[[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [1, 0, 0, 0, 1], [1, 1, 1, 0, 0]]`

정답은 3000이지만 3300이 출력되었고, 위의 알고리즘은 무조건 최소값을 기준으로 그래프를 갱신하지만 당장은 최소값이 아닐지라도 다음에 탐색할 위치에 대해서는 최소값이 생기는 경우가 발생하는 것을 확인할 수 있었다.

 

위의 예시의 (3,2)위치에서의 최소 비용은 2000이고 (2,3)에서의 최소 비용은 1700이며,

위 알고리즘에 따르면 (3,3)의 값은 2000+100 < 1700+600 이므로, (3,2) -> (3,3)의 경로의 비용인 2100으로 갱신된다.

 

하지만 (3,2) -> (3,3) -> (4,3)으로 가는 경로의 최소 비용은 2000+100+600 = 2700인데 반해,

(2,3) -> (3,3) -> (4,3)으로 가는 경로의 최소 비용은 1700+600+100 = 2400으로 결과적으로는 더 큰 비용의 값으로 갱신된다.

 

풀이 2

따라서, 종/횡의 방향 모두에서 접근해 오는 경우에는, 각 방향으로 부터의 비용값을 dictionary에 저장해놓기로 하고 다시 알고리즘을 작성하게 되었다.

def solution(board):
    from collections import deque
    d = ''
    n = len(board)
    answer = []
    board[0][0] = {'':0}
    q = deque([(0,0,d)])
    while q:
        x,y,d = q.popleft()
        for nx,ny in [(x-1,y),(x,y+1),(x+1,y),(x,y-1)]:
            if not (nx==0 and ny==0) and (0<=nx<n and 0<=ny<n) and board[nx][ny]!=1:
                if (d=='h' and x!=nx) or (d=='v' and y!=ny): # corner
                    nd = 'h' if d=='v' else 'v'
                    if board[nx][ny]==0:
                        board[nx][ny] = dict()
                        board[nx][ny][nd] = board[x][y][d]+600
                        q.append((nx,ny,nd))
                    else:
                        if not board[nx][ny].get(nd):
                            board[nx][ny][nd] = board[x][y][d]+600
                            q.append((nx,ny,nd))
                        elif board[nx][ny][nd]>board[x][y][d]+600:
                            board[nx][ny][nd]=board[x][y][d]+600
                            q.append((nx,ny,nd))
                    
                            
                else: # straight
                    nd = 'h' if ny!=y else 'v'
                    if board[nx][ny]==0:
                        board[nx][ny] = dict()
                        board[nx][ny][nd] = board[x][y][d]+100
                        q.append((nx,ny,nd))
                    else:
                        if not board[nx][ny].get(nd):
                            board[nx][ny][nd] = board[x][y][d]+100
                            q.append((nx,ny,nd))
                        elif board[nx][ny][nd]>board[x][y][d]+100:
                            board[nx][ny][nd]=board[x][y][d]+100
                            q.append((nx,ny,nd))
                        
    answer = min(board[n-1][n-1].values())
                
    return answer