[프로그래머스] 배달 (Python)

문제 링크

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

프로그래머스

소스 코드

import heapq as hq

def solution(N, road, K):
    graph = [[500001 for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        graph[i][i] = 0
    
    for a,b,k in road:
        graph[a][b] = min(graph[a][b],k)
        graph[b][a] = min(graph[b][a],k)
    
    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                graph[i][j] = min(graph[i][j],graph[i][k] + graph[k][j])
    
    answers = [x for x in graph[1] if x <= K]
    return len(answers)

해설

• 플로이드 워셜, 그래프 최단 거리 탐색

BFS로 풀이를 했다가 딱 한 개의 테스트 케이스만 통과하지 못해서 조건이 빡센 경우에 처리가 빨리 될 수 있도록 여러 가지 개선을 시도해보았으나 결국 실패했습니다.

그냥 일부러 BFS로는 오답이 나올 수 밖에 없는 구조로 문제를 만든 것 같네요..

 

관련 풀이를 찾아보면 다익스트라나 플로이드 워셜로 풀이가 되어 있었는데 공부한지 오래 되어서 복습하는 시간을 가졌습니다 ㅠㅠ

 

그래프 초기화

범위를 N+1로 설정하는 것은, 이정도의 그래프 문제에 도전하신 분들이라면 잘 알 것이라고 생각합니다.

노드의 번호를 그냥 바로 인덱스로 사용하기 위함이죠.

단, 500,001 이라는 숫자로 초기화 한 것은(대부분 10**9 와 같은 INF 값을 설정하십니다만) 문제의 조건에 K가 500,000까지라고 했기 때문입니다.

이를 초과하는 값은 애초에 고려 대상이 아니기 때문에 저 값으로 초기화 했습니다.

graph = [[500001 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    graph[i][i] = 0

 

최소 거리만 저장

min 함수를 이용해서 2차원 그래프에 저장된 값과 현재의 값을 비교하여 작은 것만 저장합니다.

문제를 보면 두 노드를 잇는 간선이 두 개 존재할 수 있다고 되어있기 때문에 불필요한 연산을 제외하기 위한 작업입니다.

for a,b,k in road:
    graph[a][b] = min(graph[a][b],k)
    graph[b][a] = min(graph[b][a],k)

 

플로이드 워셜

이건 개념을 모르면 이해할 수 없는 코드라고 생각합니다.

아주 간단히 설명하면 i 는 출발 노드, j 는 도착 노드, k 는 중간에 거쳐가는 노드입니다.

경우에 따라서 i 노드에서 바로 j 노드로 가는 것보다 i 에서 k 를 거쳐 j 로 도착하는 것이 최단 경로일 수 있습니다.

점화식으로 표현하면 min( D(i,j), D(i,k) + D(k,j)) 가 됩니다.

 

좀 더 자세히 내용을 이해하고 싶으신 분들은 이코테의 내용을 정리한 제 이전 블로그 포스팅이나 이코테 영상을 참고하시면 좋겠네요!

 

틀린 풀이

# 틀린 풀이 : 리스트 k 기준 정렬 후 break 추가해도 실패
from collections import deque

def solution(N, road, K):
    graph = [[100001 for _ in range(N)] for _ in range(N)]
    for a,b,k in road:
        graph[a-1][b-1] = min(graph[a-1][b-1],k)
        graph[b-1][a-1] = min(graph[b-1][a-1],k)
    
    new_graph = [[] for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            if graph[i][j] != 100001:
                new_graph[i+1].append((j+1,graph[i][j]))
    new_graph = [sorted(x,key=lambda x:x[1]) for x in new_graph]
    answer = bfs(new_graph,K)
    return len(set(answer))
    
def bfs(graph,K):
    answers = [1]
    queue = deque([(1,0,[1])])
    while queue:
        cur,k,visited = queue.popleft()
        for next,dist in graph[cur]:
           if next not in visited and k + dist <= K:
                answers.append(next)
                queue.append((next,k+dist,visited+[next]))
            elif next in visited and k + dist > K:
                break
    return answers