배달

🤖문제 : 배달 Lv2

😎풀이

# 플로이드 워셜
def solution(N, road, K):
    answer = 0
    INF = int(1e9)
    graph = [[INF]*(N+1) for _ in range(N+1)]
    
    # 자기 자신으로 가는길 0으로 초기화
    for a in range(1, N+1) :
        for b in range(1, N+1) :
            if a == b :
                graph[a][b] = 0
    
    # 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
    for start, end, length in road :
        graph[start][end] = min(graph[start][end], length)
        graph[end][start] = min(graph[end][start], length)
    
    # 점화식에 따라 플로이드 워셜 알고리즘 수행
    for k in range(1, N+1) :
        for a in range(1, N+1) :
            for b in range(1, N+1) :
                if k == 2 and a == 1 and b == 5 :
                    print(graph[a][b], graph[a][k], graph[k][b])
                    
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])


    for v in graph[1] :
        if v <= K :
            answer +=1 
    
    return answer

👩‍🏫접근 방식

• 플로이드 워셜
  • 다익스트라 알고리즘으로 접근했어야 했는데, 문제를 잘 못 읽고 플로이드 워셜 알고리즘을 사용했다..
  • 모든 구간에서 모든 구간으로 조건을 탐색하는 문제로 착각했었다.
  • 시간 복잡도가 $O(N^3)$인 알고리즘이지만 문제 조건상 가능했다.

섬 연결하기

🤖문제 : 섬 연결하기 Lv3

😎풀이

def find_parent(parent, x) :
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출.
    if parent[x] != x :
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b) :
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b

# 크루스칼 알고리즘
def solution(n, costs) :
    edges = []
    answer = 0
    parent = [0]*(n)
    
    # 부모 테이블 자기 자신으로 초기화
    for i in range(n) :
        parent[i] = i
    
    # 모든 간선 정보 입력
    for cost in costs :
        edges.append(cost)
    # 간선 cost별로 정렬
    edges.sort(key =lambda x : x[2])
    
    # 간선을 하나씩 확인.
    for edge in edges :
        a, b, cost = edge
        # 같은 부모를 공유하지 않을 경우에만 추가(싸이클 제거)
        if find_parent(parent, a) != find_parent(parent, b) :
            union_parent(parent, a, b)
            answer += cost
        
    return answer

👩‍🏫접근 방식

• 크루스칼 알고리즘
  • 최소 비용으로 신장 트리를 찾는 알고리즘인 크루스칼 알고리즘 사용.