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

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

 

프로그래머스

---

풀이

0.방향성 생각

• BFS로 목적지까지 탐색하기.
• 큐에 현재 (x,y,direction,line,conner) 이런식으로 추가해서 현재까지 cost 계산할 수 있게 한다.
• 재방문을 해서 최소값이 갱신되는 경우가 있다. 이 경우에는 큐에 또 추가한다.
• 여기서 주의할 점은 현재 값이 최소로 갱신되더라도 들어오는 방향에 따라서 이후에 값이 달라질 수 있다.
• 따라서 +500으로 후에 코너에서 추가되는 문제를 제거
• 밑에 다익풀이도 있음

 

1. 입력

from collections import deque

def solution(board):
    
    n = len(board)
    costs = []
    
    step = [(1,0),(0,1),(-1,0),(0,-1)] # 우,하,좌,상    
    visit = [[-1]*n for _ in range(n)]
    visit[0][0] = 0

visit에는 현재 좌표까지 필요한 cost를 업데이트 시킨다.

 

2. line, conner 업데이트

 while q:
        x,y,dire,l,c = q.popleft()
        
        for i in range(4):
            dx,dy = step[i]
            nx = x + dx
            ny = y + dy
            
            if 0<=nx<n and 0<=ny<n and board[ny][nx] == 0:
                ndire,nl,nc = i,l,c
                if i == dire:
                    nl += 1
                else:
                    nl += 1
                    nc += 1

현재 방향과 일치하는지, 일치하지 않는지에 따라 l,c를 업데이트한다.

 

3. cost업데이트

                if visit[ny][nx] == -1: # 첫방문 큐에 그대로
                    visit[ny][nx] = 100*nl+500*nc
                    q.append((nx,ny,ndire,nl,nc))
                else:
                    if 100*nl+500*nc < visit[ny][nx]+500: # 재방문은 같거나,낮은 가격일때만
                        visit[ny][nx] = 100*nl+500*nc
                        q.appendleft((nx,ny,ndire,nl,nc))
                        
            if (nx,ny) == (n-1,n-1):
                costs.append(100*nl+500*nc)

    return min(costs)

첫방문인 경우에는 현재 line 개수인 nl, conner 개수인 nc를 이용해서 계산.

재방문인 경우에는 이후 코너로 인해 발생하는 문제를 +500을 해줘서 보정한다.

목적지 도달했으면 cost 추가하기

---

전체코드

BFS

from collections import deque

def solution(board):
    
    n = len(board)
    costs = []
    
    step = [(1,0),(0,1),(-1,0),(0,-1)] # 우,하,좌,상    
    visit = [[-1]*n for _ in range(n)]
    visit[0][0] = 1
    
    q = deque([(0,0,0,0,0),(0,0,1,0,0)]) # x,y,현재방향,직선수,코너수
    while q:
        x,y,dire,l,c = q.popleft()
        
        for i in range(4):
            dx,dy = step[i]
            nx = x + dx
            ny = y + dy
            
            if 0<=nx<n and 0<=ny<n and board[ny][nx] == 0:
                ndire,nl,nc = i,l,c
                if i == dire:
                    nl += 1
                else:
                    nl += 1
                    nc += 1
                
                if visit[ny][nx] == -1: # 첫방문 큐에 그대로
                    visit[ny][nx] = 100*nl+500*nc
                    q.append((nx,ny,ndire,nl,nc))
                else:
                    if 100*nl+500*nc < visit[ny][nx]+500: # 재방문은 같거나,낮은 가격일때만
                        visit[ny][nx] = 100*nl+500*nc
                        q.appendleft((nx,ny,ndire,nl,nc))
                        
            if (nx,ny) == (n-1,n-1):
                costs.append(100*nl+500*nc)

    return min(costs)

 

다익스트라

import heapq as hq

def solution(board):
    
    n = len(board)
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    inf = 1e9
    visit = [[[inf]*4 for _ in range(n)] for _ in range(n)]
    
    heap = [(0,0,0,i) for i in range(2)] # cost,x,y,dire
    while heap:
        
        cost,x,y,d = hq.heappop(heap)
        
        if (x,y) == (n-1,n-1):
            return cost
        
        for nd in range(4):
            dx,dy = dire[nd]
            nx = x + dx
            ny = y + dy
            
            if 0<=nx<n and 0<=ny<n and not board[ny][nx]:
                
                if d==nd: ncost = cost + 100
                else: ncost = cost + 600
                    
                if ncost < visit[ny][nx][nd]:
                    hq.heappush(heap,(ncost,nx,ny,nd))
                    visit[ny][nx][nd] = ncost

다익풀이

코너돌때, 직선100 + 코너 500으로 600해줘야되는데 500해줘서 삽질좀했다.

맵이 작아서 크게 성능차이는 없는데 다익으로 푸는 풀이가 정해같긴함.

 

중요 포인트는 격자 node에서 들어오는 방향마다 다른 노드로 생각해서 visit 처리하기.

코멘트

이렇게 갱신하는 문제에서 최소값을 갱신하더라도 후에 문제가 발생하는 경우가 있어서,

찾기 쉬운 엣지케이스라 직관으로 +500 추가해줘서 맞긴했는데, 실전가면 다른 방법으로 수정할듯