Dev_Diary

https://www.acmicpc.net/problem/17472구현 + 최소 스패닝 트리 문제입니다. 구현 때문에 귀찮은 부분이 많을 뿐 사실 최소 스패닝 트리의 정석과 같은 문제입니다.해당 문제의 풀이는 크게 세 부분으로 나누어집니다. 1. 섬의 구분2. 섬 사이의 연결 탐색3. 최소 스패닝 트리 형성 1. 섬의 구분 같은 경우에는 DFS 나 BFS 혹은 Union-Find 등 그래프 탐색을 이용해 연결되어 있는 땅을 찾아주면 됩니다. 2. 섬 사이의 연결 탐색의 경우 섬의 모든 부분에서 네 방향으로 뻗어나가는 탐색 경로를 짜 가장 먼저 탐색되는 땅이 다른 섬인 경우 [현재 섬의 그룹, 다른 섬의 그룹, 거리] 의 형식으로 엣지를 형성해 기록해 줍니다. 3. 최소 스패닝 트리는 2 에서 만든 엣지를..

https://www.acmicpc.net/problem/16957그냥 시뮬레이션으로 풀 수도 있지만 조금 더 효율적으로 풀 수 있는 방법이 존재합니다.생각해보면 모든 위치에 있는 공은 몇 개의 위치로 모일 수 밖에 없습니다. 울퉁불퉁한 콘크리트 바닥에 물을 뿌리면 물이 고이는 위치가 존재하는 것 처럼 다른 위치로 이동할 수 없는 위치로 공이 모두 고이게 됩니다. 해당 위치를 찾기 위해 조건에 따라 그래프를 만듭니다. 어차피 모든 노드에서 다른 노드로 이동할 수 있는 경로는 하나뿐입니다. 그러면 우리는 그래프를 사용해 공이 이동하는 경로를 알 수 있습니다. 또 B -> A 의 경로가 있고 C -> B 의 경로가 존재한다면 C -> A 의 경로로 병합된다는 점을 고려해 Union-Find 알고리즘을 사용한..

https://www.acmicpc.net/problem/16562Union-Find 알고리즘을 사용해 풀 수 있는 문제입니다. 알고리즘을 사용해 그룹을 나눈 뒤, 각 그룹에서 가장 싼 가격을 가진 친구를 선택하기만 하면 됩니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 자신이 그룹의 대표가 아니면 if group_list[node] != node: # 재귀적으로 재탐색 group_list[node] = Find(group_list, group_list[node]) return group_list[node]# Uniondef Union(group_l..

https://www.acmicpc.net/problem/1939Union-Find 알고리즘을 사용하면 보다 간편하게 풀 수 있는 문제입니다. 최소 스패닝 트리(MST) 문제를 풀 때 사용하는 크루스칼 알고리즘과 어떻게 보면 비슷한 문제입니다.일반적으로 크루스칼 알고리즘을 풀 때 엣지를 코스트 기준으로 오름차순 정렬해 순차적으로 병합해가며 연결여부를 탐색합니다. 하지만 해당 문제에서는 모든 노드의 연결이 아닌 연결되었으면 하는 노드가 정해져 있고 최대로 옮길 수 있는 코스트를 찾는 문제이기 때문에 조금 결이 다르다고 볼 수 있습니다. 엣지를 코스트 기준으로 내림차순 정렬하면 코스트가 큰 노드먼저 연결하게 됩니다. 그렇게 순차적으로 병합하다보면 어느 순간 연결되었으면 하는 두 노드가 같은 그룹에 속하는 때..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net union-find 알고리즘의 기초 문제입니다. #include // #include #include // #include using namespace std; // 각 노드의 루트를 저장 vector root_vec; // find int find_func(int node) { // 자신의 루트가 자신이 아니면 if (root_vec[node] != node..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 유니온 파인드 알고리즘 문제입니다. 우선 주어진 데이터를 통해 트리를 구성한 뒤 유니온 파인드 알고리즘을 통해 루트노드를 병합했습니다. from collections import deque def solution(N, M, data_list, plan): # 루트 노드 리스트 union_list = list(range(N+1)) # 방문 리스트 visited = [1 for _ in range(N..