프로그래머스 그리디 문제입니다.실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간초과 (해결X)

def solution(n, costs):
    from collections import deque
    import math

    origin_graph = [cost for cost in costs]
   	
    # 최소 비용 경로를 먼저 탐색하기 위한 정렬
    origin_graph = sorted(origin_graph, key=lambda x: x[2],reverse=True)
    
    # 같은 최소 비용의 경우의 수를 고려하기 위해 deque.rotate()
    origin_graph = deque(origin_graph)
	
    # 한바퀴 돌면 끝
    rotate_cnt = 0
    minium_fee = math.inf
	
    # 힌바퀴 돌 때까지
    while rotate_cnt<n:

        graph = origin_graph.copy()

        visitied = [False for _ in range(n)]
		
        # 시작 위치 True
        visitied[graph[-1][0]] = True
        total_fee = 0

        stop_list = [graph[-1][0]]

        while graph:

            go,stop,fee = graph.pop()
			
            # 도착점 탐색X, 시작점 탐색O 시
            if not visitied[stop] and visitied[go]:
                visitied[stop] = True
                stop_list.append(stop)
                total_fee += fee
            
            # 시작점 탐색X, 도착점 탐색O 시
            elif not visitied[go] and visitied[stop]:
                visitied[go] = True
                stop_list.append(go)
                total_fee += fee

        if total_fee<minium_fee:
            minium_fee = total_fee

        rotate_cnt += 1

        origin_graph.rotate(1)

    return minium_fee

stack구조를 활용하여 최소비용을 구하는 풀이로 접근하였습니다.

먼저, 최소 비용으로 연결할 수 있는 경로를 먼저 돌기 위해 비용 순으로 정렬하였습니다.

그 다음 문제에서 입력값 [[출발,도착,비용]...] 은 양방향으로 이동할 수 있다고 가정하기 때문에 교차시켜 주어지지 않습니다. 그리하여 시작점O,도착점X or 시작점X,도착점O인 경우로 나누어 조건문을 생성하였습니다.🐰🐰🐰

하지만 위 두가지 조건문의 경우 통합된 visited 리스트에서 확인하기 때문에 시작점/도착점이 연결되어있지 않은 경우에도 요금이 추가되어 결론적으로 부적절한 풀이였습니다. 이후 구현이 어려워 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(n,costs):

    def find_parent(parent, n):
        if parent[n] != n:
            parent[n] = find_parent(parent,parent[n])
        return parent[n]
    
    def union_parent(parent,a,b):
        a = find_parent(parent,a)
        b = find_parent(parent,b)

        if a>b :
            parent[a] = b
        else:
            parent[b] = a

    
    answer = 0
    costs.sort(key=lambda x:x[2])
    parent = [i for i in range(n)]

    for node_a,node_b,cost in costs:
        if find_parent(parent,node_a) != find_parent(parent,node_b):
            union_parent(parent,node_a,node_b)
            answer += cost

    return answer

이번 문제와 같이 그래프 형태를 연결하는 최소 비용을 구하는 문제는 크루스칼 알고리즘을 활용한다는 것을 알게되었습니다.

저의 풀이처럼 최소 비용을 구하기 위해 비용을 기준으로 정렬하는 방법은 동일하되 그 후 최소 비용인 간선을 우선으로 연결하며 사이클을 형성 유무를 확인하는 방법입니다. 🐶🐶🐶

사이클 유무를 확인하기 위해 '사이클 테이블'을 만들어서 가장 끝에 연결되어있는 최소 노드(위치)가 다를 때(연결이 안되어 있을 때) 간선을 연결하는 방식입니다.

위 크루스칼 알고리즘은 처음보는 알고리즘이라 구현이 어려웠지만 이번 문제로 이해하고 넘어갈 수 있었습니다.

[다른사람의 풀이2]

def solution(n, costs):
    answer = 0
    costs.sort(key = lambda x: x[2]) 
    link = set([costs[0][0]])

    # Kruskal 알고리즘으로 최소 비용 구하기
    while len(link) != n:
        # print("link : ",link)
        # print("answer : ",answer)
        for v in costs:
            if v[0] in link and v[1] in link:
                continue
            if v[0] in link or v[1] in link:
                link.update([v[0], v[1]])
                answer += v[2]
                print("link : ",link)
                print("answer : ",answer)
                break
                
    return answer

위 풀이도 크루스칼 알고리즘을 활용한 풀이입니다. 조금 다른 점은 현재 연결된 노드들을 link라는 set()객체로 선언하고 시작점/도착점 둘 중 하나라도 연결되지 않았다고 판단되었을 시 set()을 update하는 방식입니다. 다른 코드를 보니 개념만 알고있다면 생각보다 쉽게 구현할 수 있는 문제였습니다.🐥🐥🐥

감사합니다.