[programmers/py] 배달

배달

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

문제 설명

1~N까지 각각 하나의 번호를 부여받은 마을이 있습니다.
각 마을은 양방향 통행이 가능하며 1번 마을에서 배달을 하려합니다.
이때 각 이동 시간이 K이하로 배달 가능한 마을 수를 반환해주세요.

풀이 과정

가중치와 그래프를 활용한 최단거리 알고리즘 문제

1. 각 방문 가능한 마을과 시간을 보관할 graph list 생성
   1-1. 시간을 보관할 때 1->3과 3->1의 가중치가 다를 경우 더 적은 값을 보관해야 함
2. 플로이드 워셜 알고리즘을 적용해 문제를 푼다.
3. 생성된 값의 1번 행은 1번 마을에서 각 마을까지의 최단 시간을 의미한다.

def solution(N, road, K):
    INF = int(1e9)
    graph = [[INF]*(N+1) for _ in range(N+1)]
    
    for i in range(N+1):
        graph[i][i]=0
    
    for r in road:
        x,y,w = r
        graph[x][y] = min(graph[x][y], w)
        graph[y][x] = min(graph[y][x], w)
    
    for p 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][p] + graph[p][j], graph[i][j])
    
    return len([i for i in graph[1] if i <= K] )

오답 노트

처음에는 다익스트라를 통해 문제를 해결하려함
다익스트라 알고리즘에 문제는 없었지만 양 방향 노드일 경우 최솟값을 저장하는 과정을 고려하지 못해 틀림

def solution(N, road, K):
    INF = int(1e9)
    
    graph = [[] for _ in range(N+1)] # 방문 가능한 노드
    visited = [False] * (N+1) # 방문한 노드
    distance = [INF] * (N+1) # 최단 거리

    # 방문 노드 [1,2,1] = 1->2로 가는 비용이 1
    for r in road:
        x,y,w = r
        graph[x].append([y,w])
        graph[y].append([x,w])
    
    # 다음 마을 구하기
    def small_weight() :
        min_W = INF
        index = 0
        for i in range(1, N+1):
            if distance[i] < min_W and not visited[i]:
                min_W = distance[i]
                index = i
            
        return index
    
    def dijkstra():
        distance[1] = 0 # 시작 점
        visited[1] = True
        
        # 시작 노드의 인접 가중치 변경
        for i in graph[1]:
            distance[i[0]] = i[1]
        
        for i in range(N-1):
            now = small_weight()
            print(i, now)
            visited[now] = True
            
            for j in graph[now]:
                cost = distance[now] + j[1] # 현재 최단 거리 + 이동 값
                if cost < distance[j[0]]: # 지금을 거치는 경우가 더 적을 경우
                    distance[j[0]] = cost
    dijkstra()
    
    count = len([i for i in distance if i <= K])
    return count

# 1번을 기준으로 최단거리가 K보다 작으면 count++