최소 신장 트리 (6) 썸네일형 리스트형 [백준] 1922. 네트워크 연결 - 파이썬 풀이. 최소 신장 트리 알고리즘인 크루스칼 알고리즘을 이용해서 풀면된다. 최소 비용을 구해야하는 문제이니 cost를 기준으로 graph를 정렬 시킨 후 크루스칼 알고리즘을 이용하면 어렵지 않게 풀 수 있다. 최소 신장 트리 알고리즘이 가물가물해서 한번 풀어봤다. 소스코드. " target="_blank" rel="noopener">https://gist.github.com/hanhyung6376/f6622fd34ba8c968bc12afce179c4d80.js"> [프로그래머스] 섬 연결하기 - 파이썬 섬 연결하기 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드.. 백준 2887 행성 터널 - 파이썬 문제. 풀이. 입력을 받고 좌표마다 거리를 구해서 풀었는데 메모리 초과가 나왔다. 그래서 x, y, z를 따로 입력받아서 각각 인덱스마다 최소거리를 구한다음에 크루스칼 알고리즘을 실행하면된다. 소스코드. 백준 1774 우주신과의 교감 - 파이썬 문제. 풀이. https://turret1234.tistory.com/182 백준 4386 별자리 만들기 - 파이썬 문제. 풀이. 크루스칼 알고리즘을 이용해서 풀었다. https://turret1234.tistory.com/181 백준 1197 최소 스패닝 트리 - 파이썬 문제. 풀이. 크루스칼 알고리즘 이용하여 풀었다. https://ko.wikipedia.org/wiki/.. turret1234.tistory.com 풀이랑 거의 똑같은데 이미 이어져있는 점의 입력이 들어올때 미리 union 연산을 해주면 된다. 소스코드. 백준 4386 별자리 만들기 - 파이썬 문제. 풀이. 크루스칼 알고리즘을 이용해서 풀었다. https://turret1234.tistory.com/181 백준 1197 최소 스패닝 트리 - 파이썬 문제. 풀이. 크루스칼 알고리즘 이용하여 풀었다. https://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 크러스컬 알고리즘 - 위키백과, 우리 모두의 백과.. turret1234.tistory.com 랑 거의 유사한 문제이다. 입력 값 대로 거리를 계산해서 그래프를 만드는 부분을 제외하면 똑같다. 소스코드. 백준 9372 상근이의 여행 - 파이썬 문제. 풀이. bfs를 통해서 풀었으나, 간선의 가중치가 없고 모든 간선이 연결되어있다면 노드갯수-1을 출력해도 정답이다. 소스코드. 이전 1 다음
