# 유니온 파인드
사이클 게임 20040
유니온 파인드를 활용하여 하나씩 같은 집합에 넣어준다. 넣어주기 전에 찾기를 활용하여 같은 루트에 있는 것이 확인되면 그 값을 출력해준다.제출했을 때 시간이 오래 걸려서 실수했나 싶었다. 다른 사람의 풀이를 보니 입력을 다 안 받고 반환하거나 반복문을 나오는 형식으로
친구 네트워크 4195
문자열이 입력으로 주어지기에 Map같은 해시를 사용하여 숫자로 변환해주고 유니온 파인드를 하면 된다. 루트 집합에 몇 명이 속한지 저장해주고 다른 집합과 합칠 때 넘겨주거나 넘겨받으면 된다.반례도 다 맞았는데 5%에서 틀려서 이해가 안 됐다.여러 가지를 확인해보다 pa
여행 가자 1976
여행 경로로 선택된 도시들이 연결됐는지 확인하는 문제이다.유니온 파인드를 활용하여 연결됨을 표시해주면 된다.유니온 파인드를 활용해 연결된 도시들을 하나의 그룹으로 만들어준다. 이후 여행 경로를 확인할 때 처음 받는 값으로 어떤 그룹에 속한지 확인하고 나머지 그룹도 같은
집합의 표현 1717
유니온 파인드를 사용하면 풀리는 문제이다. 수의 기준을 잡아 더 큰 수 또는 더 작은 수를 루트로 올리고 다른 집합은 연결해주는 방식을 하면 된다.집합에 루트를 찾는 과정에선 경로 압축을 해주면 된다.같은 집합인지 확인해줄 때 자주 사용되는 유니온 파인드를 알아두면 좋
[Python] 유니온 파인드 (Union Find)
그래프 알고리즘, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘서로소 집합, 상호 베타적 집합(Disjoint-Set = 서로 공통 원소가 없는 집합)으로도 불린다.노드를 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.=> 즉, 노
[백준] 다리 만들기 2
N x M 의 이차원 공간에서 섬은 1로 바다는 0으로 표시되는 정보를 바탕으로 섬간에 가장 짧은 거리의 다리를 두어 모든 섬을 이동할 수 있도록 해야하는 문제이다.
[백준] 4803 트리
이 문제는 주어진 테스트 케이스 당 정점의 개수와 간선 정보를 기반으로 만들어지는 그룹 중 트리구조의 그룹의 개수를 반환하면 되는 문제이다.