📁문제 풀이

[Python] 백준 21924 도시 건설 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 작성 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) parent = [i for i in range(N..

[Python] 백준 19368 행성 연결 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/19368 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 작성 코드 import sys input = sys.stdin.readline n = int(input()) edges = [] # 비용 오름차순을 위한 리스트 parent = [i for i in range(n+1)] # 서로소 집합 (본인을 부모로 갖도록 초기화) f..

[Python] 백준 14621 나만 안되는 연애 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 문제 - school : 정점 별 학교 성별 - parent : 정점 별 서로소 집합 정보 - edges : 간선의 비용 기준으로 오름차순 정보 저장 - 정렬된 edges를 순차적으로 접근하며 사이클이 발생하지 않으면 연결 - 서로소 집합이 정점 본인과 같은 정점의 개수..

[Python] 백준 6497 전력난 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 해결 포인트 - 크루스칼 (최소 스패닝 트리) 알고리즘 - find 함수 : 부모 노드(어느 집합에 속하는지) 확인 - union 함수 : 정점 a, b를 같은 집합에 속하도록 parent 업데이트 - 여러 테스트케이스 있으므로 n, m이 0, 0 일때 종료 조건으로 무한 반복 - edges : 간선을 비용 기준 오름차순으로 저장 - parent : 각 ..

[Python] 백준 4386 별자리 만들기 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 포인트 - 크루스칼 (최소 스패닝 트리) 알고리즘 - alist : 각 정점의 x, y 정보 저장 - edges : 정점 간 모든 간선 길이( sqrt((x1 - x2)**2 + (y1 - y2)**2) ) 를 오름차순으로 저장 - parent : 집합정보 ( 연결된 정점 정보) - find 함수 : 같은 집합에 속해있는지 확인 - unio..

[Python] 백준 1922 네트워크 연결 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 (최소 스패닝 트리 알고리즘) - 서로소 집합을 위한 find_parent, union_parent 함수 - edges : 간선 비용, 간선a, 간선b를 저장하여 오름차순으로 저장 - parent : 각 정점 별 집합 정보 저장 - 정렬된 edges 를 하나씩 방문하며 사이클이 발생하지 않는다면 간선 연결 - find_parent(a) != find_parent(b) 즉, 같은 집합에 속해있지 않다 ..

[Python] 백준 1647 도시 분할 계획 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 포인트 - 최소 스패닝 트리 문제 (크루스칼 알고리즘) - edges : 간선 비용을 오름차순으로 저장할 리스트 - parent : 서로소 집합 정보 저장할 리스트 - find_parent(x) : 서로 같은 집합에 속해있는지 확인하는 함수 - union_parent(a, b) : a, b 정점에 대해..

[Python] 프로그래머스 순위 | 플로이드-워셜 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 포인트 - 플로이드 워셜 알고리즘으로 해결 가능한 문제 - 정점 i가 1부터 N까지 모든 정점으로 갈 수 있다면 순위를 알 수 있다. - 초기 인접 행렬은 무한수로 초기화, 연관이 있는 두 정점 results는 1로 초기화한다. 이는 1번에 걸쳐 a 정점과 b 정점이 관계가 있다는 뜻이다. - a 정점에서 b 정점으로 바로 가는 방법 (a..

[Python] 백준 1197 최소 스패닝 트리

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해결 포인트 - 문제 이름에서 알 수 있듯 최소 스패닝 트리 알고리즘 문제입니다. - parent : 서로소 집합 개념에서 각 정점이 어느 집합에 속해있는지 정보를 저장 - edges : 간선의 정보를 저장하는 공간. 가장 작은 비용이 발생하는 간선부터 연결해나간다 - find_parent : 해당..