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

문제보기 

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

프로그래머스

 

풀이 & 코드 

일단 삽질을 좀 많이 했다... 그래서 그런지 코드가 그렇게 이쁘지는 않은 거 같다ㅠ 이 글을 보시는 분들은 이렇게 짠 사람도 있구나 하고 넘어가주면 좋을 것 같다! 

 

그리고 설계사 죠르디는 의뢰를 골라 받는 센스가 필요해 보인다ㅎ

 

설계사 죠르디

 

문제를 처음 보고 든 생각은 dijkstra였다. 최소인 비용인 칸을 골라 한칸씩 전진해 n-1, n-1 까지 도착하는 것을 목표로 삼아 코드를 작성했다. 따라서 2차원 배열을 만들어 최소 cost랑 directions을 각가 저장해 다음과 같이 코드를 짰다.

 

import math

def solution(board):
    n = len(board)
    directions = [[[] for _ in range(n)] for _ in range(n)]
    costs = [[math.inf for _ in range(n)] for _ in range(n)]
    dx = [1,-1,0,0]
    dy = [0,0,-1,1]
    directions[0][0] = [0,3]
    costs[0][0] = 0
    
    x, y = 0, 0
    cost = costs[x][y]
    while True:
        if x == n-1 and y == n-1:
            break
            
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:
                add_cost = 100 if d in directions[x][y] else 600
                if cost + add_cost <= costs[nx][ny]:
                    costs[nx][ny] = cost + add_cost
                    directions[nx][ny] += [d]
        
        board[x][y] = 1
        cost = math.inf
        for r, row in enumerate(costs):
            for i, el in enumerate(row):
                if el < cost and board[r][i] == 0:
                    cost = el
                    x, y = r, i
                    
    return cost

 

당연히 틀렸다!ㅎㅎ 제출했을 때 70점 정도 맞았다.  결론적으로 틀린 이유는 현재 칸의 방향과 다음 칸의 방향에 따라 더해지는 값이 달라지기 때문에 최소값 하나만 저장하는 것이 아닌 모든 방향에 따른 최솟값을 저장해 주어야한다. 다시말해 기존과 같은 방향의 cost에 100을 더한 것과 다른 방향에서의 cost에 600 더한 것을 비교해 주어야 하고 그러기 위해서는 모든 방향에 따른 값들을 저장해 주어야 한다! 이 내용을 깨닫고 코드를 보니 애초에 dijkstra 알고리즘은 해당 문제와 맞지 않는다... 하지만 코드 짠게 아까워서 완전히 갈아엎지는 못하고 수정을 해 보았다.

 

import math

def solution(board):
    n = len(board)
    inf = [[[[math.inf, -1]] for _ in range(n)] for _ in range(n)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    inf[0][0] = [(0,0), (0,1)]
    
    x, y = 0, 0
    while True: 
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            # 다음 칸이 범위를 벗어나거나 벽이 아닌 것을 체크
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 1:
                costs = inf[x][y]
                cost = math.inf
                
                # 기존 칸에서 현재 칸 넘어올때 방향을 고려해 무엇을 더하는 게 쌀지
                for i in range(len(costs)):
                    add = 100 if costs[i][1] == d else 600
                    cost = min(cost, costs[i][0]+add)
                        
                # 새로운 칸에 해당 방향이 존재하는지 존재하면 더 작은 걸로 
                ncosts = inf[nx][ny]
                for i in range(len(ncosts)):
                    if ncosts[i][1] == d:
                        ncosts[i][0] = min(cost, ncosts[i][0])
                        break
                else: # 이미 check되었던 곳이지만 새로운 비용이 원래 비용보다 600이하면 check를 해제하고 다시 확인
                    if board[nx][ny] == 2 and cost - min(list(zip(*inf[nx][ny]))[0]) < 600:
                        board[nx][ny] = 0
                    
                    # 새로운 비용와 방향 추가
                    inf[nx][ny] += [[cost, d]]
        
        # board = 2로 바꿔 해당 칸은 check 되었음을 나타냄
        board[x][y] = 2
        
        # check되지 않은 칸 중에 가장 비용이 낮은 값으로 다음 칸 설정
        # 해당되는 칸이 없다면 모든 경우의 수를 다 돌았다고 판단. 함수 종료
        cost = math.inf
        flag = False
        for r, row in enumerate(inf):
            for i, el in enumerate(row):
                if board[r][i] == 0:
                    for c, d in el:
                        if c < cost:
                            cost = c
                            x, y = r, i
                            flag = True
        
        if flag == False:
            break
            
    return min(list(zip(*inf[n-1][n-1]))[0])

 

이해를 위해 주석을 추가했다. 가장 크게 달라진 점은 inf라는 다차원 배열은 다음과 같이 구성했다.

inf[세로위치][가로위치][방향과 해당 방향에서의 최소 cost의 리스트]  이런 식으로 방향과 최소비용을 저장했고. dijkstra 틀을 유지해 최소비용을 가진 칸을 선정하는 부분도 변형시켰다. 필자가 생각하는 중요 문장은 다음이 아닐까 싶다. 해당 문제에서 dijkstra알고리즘을 쓰려면 꼭 필요하다!

 

if board[nx][ny] == 2 and cost - min(list(zip(*inf[nx][ny]))[0]) < 600:
	board[nx][ny] = 0

 

해당 칸이 check된 칸이고 새로 추가될 cost가 기존 최소 cost랑 600이하로 작다면 해당 칸을 다시한번 dijkstra를 돌리라는 의미이다. 해당 문장을 추가한 이유는 해당 칸을 기준으로 본다면 최소이지만 최종 위치를 기준으로 본다면 최소가 아닐 수도 있다.

 

 

해당 그림에서 빨간선이 최소비용을 가진다. 하지만 형광색을 기준으로 봤을 때 파란색을 통해 도착한 값은 5200, 빨간색을 통해 도착한 값은 5000이다. 즉 형광색만 기준으로 보면 파란색이 더 비용이 적지만 그 다음 칸으로 가게되면 5300/ 5600으로 빨간색이 최소비용을 가진다는 것을 알 수 있다. 따라서 형광색 위치에서 최소 비용 5000으로 dijkstra알고리즘을 돌렸어도 차가 600이하인 5300이라는 비용이 새로 들어오면 다시 dijstra알고리즘을 돌려야 한다!

 

 

후기

오랜만에 제대로 삽질한 문제다.. 풀이는 쉽게쉽게 한 것 같지만 사실은 몇시간 걸려서 풀었다.ㅎ 처음 문제를 해석할 때 방향을 잘못 잡았다. direction에 따라 값이 달라지기 때문에 dijkstra보다는 bfs로 최소 cost를 계산하는 방식이 더 맞는 것 같다. 나중에 bfs로 다시 풀어봐야지ㅎ