Algorithm/Graph188 [파이썬] 프로그래머스 : 섬 연결하기 (Lv.3) [파이썬] 프로그래머스 : 섬 연결하기 (Lv.3) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0. 방향성 생각 최소 비용으로 모든 섬을 연결하는 문제. 최소 스패닝 트리랑 같은 맥락이다. 1. 함수 작성 def solution(n,costs): costs.sort(key=lambda x:x[2]) parent = [i for i in range(n+1)] def find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x] de.. 2023. 7. 5. [파이썬] 백준 9694 : 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (골드3) [파이썬] 백준 9694 : 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (골드3) 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 dist[x_node]: # 시작점 까지 거리 크면 패스 continue for nx_node,weight in graph[x_node]: # 그렇지 않은 경우 nx_dist = x_dist + weight # nx까지 거리 = x까지 거리+ 가중치 if nx_dist < dist[nx_node]: # 새로운 경로가 이득이면 업데이트 dist[nx_node] = nx_dist # 다음 노드까지 걸리는 비용 path[nx_node] = x_node # 어디서 왔는지 업데이트 heapq.heappush(q,(nx_dist,nx_node)).. 2023. 7. 3. [파이썬] 백준 1647 : 도시 분할 계획 (골드4) [파이썬] 백준 1647 : 도시 분할 계획 (골드4) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 풀이 0. 방향성 생각 도시가 최소한의 비용으로 연결되는 경우이므로 최소 스패닝 트리를 생각한다. 여기서 간선의 가중치가 가장 높은 부분을 제거하면 마을이 두 개로 나누어진다. 1. 입력 받기 import sys input = sys.stdin.readline house,path = map(int,input().split()) graph = [] for i in r.. 2023. 6. 30. [파이썬] 백준 1260 : DFS와 BFS (실버2) [파이썬] 백준 1260 : DFS와 BFS (실버2) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 풀이 0.방향성 생각 탐색 시 순번이 낮은 노드부터 탐색하므로 입력을 받은 후 정렬하는 과정이 필요함 1. 입력 from collections import deque import sys input = sys.stdin.readline node,line,start = map(int,input().split()) arr = [[] for i in range(node+1.. 2023. 6. 3. 이전 1 ··· 40 41 42 43 44 45 46 47 다음
