민규의 흔적

2024년 6월 18일문제 링크 : 프로그래머스 - 섬 연결하기 문제 접근 모든 섬을 최소 비용으로 연결했을 때, 해당 비용을 출력하는 문제이다. 이어져있지 않은 섬은 존재하지 않기에, 최소 신장 트리(MST)를 찾는 문제라고 판단해 크루스칼 알고리즘을 활용하고자 하였다. 다음과 같은 그래프가 있다고 가정해보겠다.  모든 간선의 정보를 비용을 기준으로 오름차순 정렬하고, 각 노드의 루트 노드 정보를 담을 배열을 선언 및 초기화, MST의 총 길이를 나타내는 length를 선언한다. 두 노드 중 어느 노드를 부모 노드로 할 지 통일시켜주기 위해, 번호가 더 작은 노드를 부모노드로 지정하는 것으로 통일시켜주겠다. 이제부터, 각 간선의 정보를 앞에서부터 확인하며 탐색을 진행해보자.  0번 노드와 1번 노드의 ..

2024년 6월 18일문제 링크 : 프로그래머스 - 가장 먼 노드 문제 접근 1번 노드에서 가장 먼 노드의 개수를 구하는 문제다. 한 노드에서 다른 노드들까지의 거리(one to all)를 구하는 문제라고 판단되어 다익스트라 알고리즘을 활용해야겠다 생각하였다. 모든 간선의 길이를 1로 간주하고 1번 노드에서 각 노드까지의 거리를 모두 계산한 후, 가장 먼 거리의 노드 개수를 출력하였다. 전체 코드 from collections import dequedef solution(n, edge): answer = 0 INF = 50001 graph = [[] for _ in range(n + 1)] for e in edge: graph[e[0]].append(e[1]) ..