WannaBeDeveloper

20040번: 사이클 게임 www.acmicpc.net 이 문제는 그래프에 간선을 차례대로 그릴 때 언제 사이클이 처음으로 생기는지를 묻는 문제이다. 만약 모든 간선이 동시에 주어진 상태에서 사이클 유무를 물었다면 그래프를 그리고 그래프 탐색을 통해 사이클 유무를 따져도 되지만, 이 문제는 간선을 하나씩 그리면서 사이클 유무를 따져야 하기 때문에 만약 단순히 그래프 탐색을 통해 사이클 유무를 따진다면 m번의 그래프 탐색을 반복해야 하고, 이는 매우 비효율적이다. 그래서 이는 그래프 탐색이 아닌 분리 집합을 이용해 해결한다. 만약 어떤 간선이 주어졌을 때 그 간선 위의 두 점이 속한 집합이 같은 경우 그 간선 없이도 두 점이 서로 연결되어 있음을 의미하는데, 만약 그 간선을 추가한다면 두 점 사이의 경로가..

4195번: 친구 네트워크 www.acmicpc.net 이 문제는 친구 관계가 생긴 순서대로 주어졌을 때 두 사람의 친구 네트워크에 몇 명이 있는지를 구하는 문제이다. 얼핏 보면 두 사람의 친구 네트워크에 각각 몇 명이 있는지를 묻는 것처럼 보여 실제 출력은 각 사람의 친구 네트워크 인원 수로 2개의 숫자를 출력해야 하는 것처럼 보이지만, 결국 두 사람이 주어졌을 때 두 사람은 같은 친구 네트워크에 속하게 돼 동일한 인원 수를 가진다. 따라서 1개의 숫자만 출력해도 된다. 이 문제는 분리 집합을 친구 네트워크를 나타내는데 사용하면 해결할 수 있다. 다만 이전의 분리 집합 문제처럼 임의의 두 원소가 주어졌을 때 두 원소가 같은 집합에 있는지를 묻는 게 아니라 그 두 원소가 들어있는 집합을 합한 뒤 그 집합..

1976번: 여행 가자 www.acmicpc.net 이 문제는 도시들이 정점으로 주어진 그래프에 대해 여행 계획이 주어진 경우 그래프 내 간선을 통해 해당 여행 계획을 실천할 수 있는지를 묻는 문제이다. 이를 달리 해석하면 여행 계획 내 도시들이 그래프 내에서 모두 연결되어 있는지를 묻는 문제로, 이는 그래프 탐색을 통해 여행 계획 내 정점들이 모두 연결되어 있는지를 확인함으로써 해결할 수 있다. 즉, 우선 여행 계획 내 한 도시에 대해 DFS나 BFS를 실행한 뒤에, 여행 계획 내 나머지 도시들을 방문했었는지를 검사하면 된다. 그러나 이 문제는 다른 방식으로도 해결할 수 있는데, 바로 분리 집합을 이용하는 것이다. 우선 각 도시에 대해 그 도시를 유일한 원소로 가지는 집합을 만든다. 그 다음 만약 두 ..

1717번: 집합의 표현 www.acmicpc.net 이 문제는 집합을 코드 상에서 어떻게 표현하는지에 관한 문제이다. 여기서 집합을 사용하는 목적은 임의의 두 원소가 주어졌을 때 두 원소가 들어있는 집합을 합한다던가(합집합 연산을 의미한다.), 아니면 두 원소가 같은 집합 내에 있는지를 판별하기 위함이다. 이를 구현하기 위해서는 가장 단순하게는 그냥 파이썬 내의 집합 자료 구조를 사용해서 위 연산을 구현하면 되지만, 문제는 합집합 연산의 경우 어떤 집합을 합쳐야 하는지를 알려주는게 아니라 집합 내의 한 원소만을 알려주기 때문에 모든 집합들을 뒤져서 그 원소가 들어있는 집합을 찾아야 한다. 그러므로 이러한 방식은 매우 비효율적인 방법이 된다. 이러한 집합을 표현하는 방법으로는 집합을 하나의 트리로 구현하..