union-find
[백준] 16724. 피리 부는 사나이 - Python
[Gold III] https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 Union-Find(Disjoint Set)를 이용하여 풀 수 있는 문제라는 것만 캐치한다면, 어렵지 않게 풀이할 수 있었던 문제. NxM 지도의 각 칸에 번호를 지정하고, (좌표가 r, c 일 때, 칸의 번호를 r * M + c 로 지정.) 그 번호를 기반으로 root를 저장하는 dictionary를 초기화. Union, Find 함수..
[백준] 1922. 네트워크 연결 - Python
[Gold IV] https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 기본적인 MST(Minimum Spanning Tree) 문제. Kruskal 알고리즘을 통해 MST를 구현하였다. 응용된 것 없이 MST를 구현하기만 하면 되는 문제이므로 설명은 생략. AC. from collections import deque # input N = int(input()) M = int(input()) root = {i: i for i in range(1, N+1)} edges = [] for _ in range(M): a, b, c = map..
[백준] 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를 이용한 풀이..
[프로그래머스] 표 병합 - 파이썬
2023 KAKAO BLIND RECRUITMENT - 150366. 표 병합 [Lv. 3] https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1 일단 50x50 셀이라는 부분에서, UPDATE value1 value2 명령어 자체는 Brute-Force로 해결할 수 있다는 생각이 들었고, 결국 MERGE 와 UNMERGE 를 처리하는 것이 관건인 것 같았다. 사실 보자마자 떠오른 방법은 Union-Find를 이용하는 것이였는데, 그냥 모..
[백준] 1647. 도시 분할 계획 - python
[Gold IV] 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 풀이 문제를 딱 보고서 생각한 것 -> Minimum Spanning Tree구나. MST를 구현하고 나서, 남은 edge들 중 가장 value가 높은 것을 제거하면 될 것 같다. line 13의 = 를 ==로 오타내서 찾는데 시간 좀 씀...ㅎ 아무튼 clear. from collections import deque N, M = map(in..
[프로그래머스] 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:..