처음에 문제를 보고 든 생각은 다음과 같다. 연결 되어 있냐/ 연결되어 있지 않냐를 판단하는 것이므로 Union-Find를 생각했다. 하지만, 중간에 간선을 지우는 상황이 발생하는데 먄약 Path-compression을 하게 되면 문제가 발생한다는 것을 파악하였다. 그래서 Union by rank만 진행해서 Union-Find를 진행하였다. 하지만 결과는 시간 초과였다. 그런데 잘 생각해보면, 애초에 시작할 때 지워질 간선을 무시하고 Union-Find를 진행하고 나중에 Merge시키면 되는 문제였다. 다른 블로그를 참고해보니 query 배열을 잡아서 하던데, 일단 코드에서는 stack를 2개 잡아서 진행하였다.(생각해보니 좀 비효율적인듯..) 코드는 다음과 같다. #include #include #in..

사실 이 문제를 보고 가장 먼저 든 생각은 최소 스패닝 트리의 해법과 비슷하게 풀면 된다는 것이다. 특히 Kruskal 알고리즘 해법과 되게 비슷한 느낌이 들었다. 정확하게 이 문제는 스패닝 트리를 구하는 것이 아니다. 왜냐하면, 출발과 목적 지점을 포함하기만 하면 되지 모든 노드들을 전부 방문할 필요는 없기 때문이다. 하지만 Kruskal 알고리즘 기법을 활용하겠다고 마음을 먹은 이유는 다음과 같다. 1. 결과적으로 길이 최대가 되게끔 계속해서 만들어야 한다. 2. 즉 이러한 알고리즘은 사실상 최소 값들을 priority_queue에 저장하고 탐욕적으로 집합을 만드는 Kruskal 알고리즘과 매우 유사하다. 3. 또한 연결되었다는 것은 하나의 집합으로 볼 수 있다는 의미이고 상호 배타적 집합에서 배운 ..