disjoint set

[백준] 4195. 친구 네트워크 - Python

[Gold II] https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 Union-Find를 이용한, 서로소 집합(Disjoint Set) 응용 문제. 기존 Union-Find를 이용한 기본적인 문제와 크게 다르지 않으나, 네트워크에 속한 친구의 수를 따로 계산해줘야 한다. (rank와는 다름.) 네트워크에 속한 친구의 수를 기록하는 dictionary를 선언하고, (cnt) union해 주는 과정에서, root가 되는 쪽에다 다른 ..

[백준] 20040. 사이클 게임 - Python

[Gold IV] https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 Union-Find를 이용한, 서로소 집합(Disjoint Set) 문제. Union-Find를 잘 구현하고, 이를 이용해 사이클이 생겼는 지를 각 반복마다 확인하면 된다. Union-Find 알고리즘을 알고 있다면 다른 설명이 필요하지 않으므로, 생략. AC. from collections import deque n, m = map(int, input().split(..

[백준] 1043. 거짓말 - 파이썬

[백준] 1043. 거짓말 - 파이썬 [Gold IV] https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제.. 풀고 보니 Union-Find(Disjoint Set)을 이용해 풀 수 있는 문제였다. 근데 그냥 Set 이용해서 풀린 문제.. ^ㅁ^ 최대 수가 50이라 TLE가 날 일이 별로 없었기에 가능하지 않았나 싶다. 아마 Set의 intersection()과 union()을 이용해서 시간 단축이 좀 된 것 같다. Union-Find를 이용한 풀이..

[프로그래머스] 64063. 호텔 방 배정

2019 카카오 개발자 겨울 인턴십 - 64063. 호텔 방 배정 Python 풀이 풀이 Union-Find 알고리즘을 이용하여 풀면 될 것이라고 직감이 왔다. [백준] 10775. 공항 문제와 굉장히 유사했기 때문. 그런데 이제, 효율성을 위해 알고리즘을 조금 바꿀 필요가 있었다. Find는 그대로 두지만, Union하는 과정에서, 무조건 숫자가 높은 쪽이 root가 되도록 하는 것. 그렇게 하고, n번의 방이 찰 때마다, n과 n+1을 Union하는 방식으로 진행한다. 이 예시에서는, k = 10 room_number = [1,3,4,1,3,1] 맨 처음엔 dictionary가 이 상태일 것이다. {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10:..