분리집합
-
[백준] Python - 친구 네트워크메모/알고리즘 2022. 3. 25. 15:20
4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net Union-Find를 사용하는 분리집합 문제이다. 항상 보면 BFS/DFS 같은 문제나 분리 집합 문제들은 기본적인 형태가 유사한 것 같다. 다만 이 문제는 한가지 고려 사항이 있다. 친구 관계가 입력으로 주어지는데 이 친구들의 이름이 문자열로 입력된다. 여기서 나는 두 가지를 고려했다. 1. 부모 노드를 배열이 아닌 딕셔너리로 저장할 것 2. 이름을 정수로 매핑할 딕셔너리를 새로 생성할 것 부모 노드를 문자열 딕셔너리를 통해서만 확인하면 시간초과가 ..
-
[백준] Python - 여행 가자메모/알고리즘 2022. 3. 25. 15:15
1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Union-Find를 쓸 수 있는 기본적인 분리 집합 문제이다. 여행을 가려는 사람은 왔던 도시를 다시 거칠 수 있고 입력의 마지막으로 주어진 모든 도시를 갈 수만 있으면 된다. 기본적인 Union-Find를 사용하여 부모 노드를 연결하고 같은 부모를 가진 집합이라면 서로 연결되었다고 볼 수 있다. GitHub - Floodnut/algorithm: 알고리즘 풀이 모음 알고리즘 풀이 모음. Contribute to Floodnut/algorithm develop..