목록유니온 파인드 (4)

개미의 개열시미 프로그래밍

[알고리즘] 백준2644 촌수계산 - 파이썬

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net [실패한 유니온 파인드 풀이 코드] # 유니온 파인드로 풀어봄 parent = [i for i in range(n+1)] cnt_list = [0 for _ in range(n+1)] def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] de..
알고리즘/DFS, BFS, 백트래킹 2021. 9. 11. 17:13
[알고리즘] 백준20040 사이클 게임 - 파이썬

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net [풀이 코드] from sys import stdin input = stdin.readline n, m = map(int, input().split()) parent = [i for i in range(n)] def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent..
알고리즘/유니온 파인드, 최소 신장 트리(크루스칼) 2021. 9. 10. 15:44
[알고리즘] 백준4195 친구 네트워크 - 파이썬

단계별 풀기의 유니온 파인드 세 번째 문제이다. 전에 풀었던 두 문제와 달리 배열을 예제 입력 시에 해줘야 된다는 점이었다. find함수와 union함수도 좀 다르게 구현했어야 했다. (결국 다른 분의 블로그를 보고..ㅜ) https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net [풀이 코드] from sys import stdin input = stdin.readline def find(x): if parent[x] != x: parent[..
알고리즘/유니온 파인드, 최소 신장 트리(크루스칼) 2021. 9. 9. 19:41
[알고리즘] 백준1976 여행가자 - 파이썬

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net [풀이 코드] from sys import stdin input = stdin.readline n = int(input()) m = int(input()) 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..
알고리즘/유니온 파인드, 최소 신장 트리(크루스칼) 2021. 9. 8. 15:16
Prev 1 Next