처음에 문제를 보고 든 생각은 다음과 같다. 연결 되어 있냐/ 연결되어 있지 않냐를 판단하는 것이므로 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. 또한 연결되었다는 것은 하나의 집합으로 볼 수 있다는 의미이고 상호 배타적 집합에서 배운 ..

스패닝 트리 변형 문제이다. 기본적인 아이디어는 다음과 같다. 1. MST를 구한다. (Maximum cost Spanning Tree와 Minimum cost Spanning Tree)를 구해주면 된다. 2. 이를 통해 스패닝 트리가 가질 수 있는 minimum과 maximum을 구한다. 3. 만약 k가 이 값 사이에 존재하면 사이값 정리에 의하여 존재성을 담보할 수 있다. 이유에 대해서 간략하게 살펴보면 다음과 같다. Spanning Tree에 간선을 하나 추가하게 되면 무조건 사이클이 나오게 된다. 이 상황에서 하나를 지우면 또다른 스패닝 트리가 되는데 가능성은 +-1과 0이다. 즉, 사잇값 정리에 의해서 반드시 존재성을 담보할 수 있다. 코드는 다음과 같다. #include #include #in..

전형적인 Minimum cost Spanning Tree (최소 스패닝 트리) 문제이다. 모든 지점이 연결되어야 한다는 측면에서 스패닝 트리이고, 최소 비용을 구하는 상황이므로 최소 스패닝 트리이다. 최소 스패닝 트리는 Prim 알고리즘과 Kruskal 알고리즘이 있는데, 일반적으로는 Kruskal 알고리즘을 많이 사용한다. 해당 알고리즘을 요약하자면 다음과 같다. 1. Cost 순서대로 정렬한다. 2. Cost 순으로 방문하되, 연결된 집단끼리는 하나의 집단을 형성한다. (만약 동일한 집단끼리 연결되는 경우에는 해당 경로를 제외해주면 된다.) 3. 결과적으로 모든 노드들이 하나의 집합을 형성하게 될 때 Minimum cost를 만족하게 된다. 이때, 집합에 속하냐 속하지 않냐를 기준으로 구현하는 양상을..

이 문제에서 점프해서 이동할 수 있다는 것의 의미는 같은 집합 안에 들어갈 수 있는지 여부이다. 이를 활용하기 위해서 기본적으로 집합 안에 들어갈 수 있는지 여부를 판단해주면 된다. 따라서 시작 값을 기준으로 해서 정렬해주면 된다. 해당 집합의 마지막 끝자락이 판단할 직선의 시작점보다 더 뒤에 있으면 동일한 집합으로 간주할 수 있다. 크게 2가지 방법으로 처리할 수 있다. 1. DisjointSet 안에 start minimum, end maximum을 따로 저장 2. 그때그때마다 end maximum을 동기화 다만 아래의 풀이는 2번째 방법으로 코드를 구현하였다. #include #include #include #include #include #include using namespace std; typ..

전형적인 유니온-파인트(DisjointSet) 문제이다. 왜냐하면, 사이클이 형성된다는 것의 의미는 사실 상 점들의 집합에 속하는 것끼리 연결했다는 것을 의미하기 때문이다. 즉, 해당 집합에 속하는지 속하는지 않는지를 배타적으로 판단해주어야 한다. 이러한 측면에서 Disjoint Set(상호 배타적 집합)을 잡았어야 한다. 기본적인 알고리즘은 다음과 같다. 1. Union-Find algorithm을 사용한다. Init > find > merge 함수를 구현한다. 다만, 이 방법을 사용할 때 Union by rank, Path compression을 활용하여 Time complexity를 O(lg*n)로 낮춘다. 2. 사이클을 형성한다는 것의 의미는 두 점이 이미 같은 집합 안에 들어와있는 경우이다. 즉..

사실상 이 문제를 풀기위한 알고리즘 및 자료구조를 학습하고 문제를 풀게 되었다. 특히 이 문제를 풀기 위해서 유니온 파인트 자료구조가 필요한데, 해당하는 내용은 종만북 2권 25.1에 나와있으니 잘 복습하도록 하자. 이 문제를 상호 배타적 집합으로 간주해도 되는 이유를 이해하는 것이 훨씬 더 중요하다. 사실상 도킹이 되거나 안되거나 둘 중 하나의 상황으로 이어지므로 이를 상호적 배타 집합으로 이해할 수 있다. 이러한 측면에서 유니온 파인드 자료구조를 활용하는 느낌으로 이해하면 될 듯 싶다. 이 문제는 자주 복습하면서 종만북을 참고하도록 하자. #include #include #include using namespace std; int G, P; struct DisjointSet{ vector parent..

사실 이 문제를 잘못 독해해서 시간이 엄청 걸렸다.. 문제에서 다른 노선에 포함 되어있는 것을 지운다고 하였는데, 이 의미를 잘못 이해하였다. 접근 방법은 다음과 같다. 1. 제일 긴 노선을 찾는다. 2. 제일 긴 노선의 출발점을 원점으로 변경한다. (기준점 설정) 3. 출발이 빠른 순으로 정렬한다. 4. 노선들을 순차적으로 방문하되, 이전 도착점보다 도착점이 더 먼 경우에만 해당 노선을 남겨둔다. (그렇지 않으면 이전 노선에 포함된다는 의미이므로 지워도 무방하다.) 추가적으로 원형 노선에 대해서 살펴볼 필요성이 존재한다. 원형 노선의 경우, 강제로 직선 노선으로 변경해주면 된다. 예를 들어 N이 10이고 (5, 2)의 경우에는 강제로 (5, 12)로 만들어주면 직선 노선화시킬 수 있다. 이 문제에서는 ..