문제를 이리저리 돌려가면서 상황을 파악해가면 다음과 같은 상황임을 이해할 수 있다. "우주 정거장의 x, y 좌표 사이에 다른 우주 정거장이 존재하면 이동할 수 있다." 그런데, 문제에서는 질문에서 주어진 우주 정거장 사이의 이동 가능 여부를 물어보고 있으므로 일종의 위의 명제의 참/거짓 여부의 연결 양상을 판단하라고 하는 것과 동치이다. 따라서 위 문제가 상호 배타적 집합임을 파악할 수 있다. 따라서 Union-Find로 문제를 풀어주면 된다. 이 문제의 경향성은 백준 17619번 개구리 점프와 매우 유사한 양상을 띄고 있다. (viyoung.tistory.com/132) 다만, 이 문제에서는 x, y좌표를 모두 고려해야 하기 때문에 x기준으로 union, y기준으로 union을 시켜주면 된다. 추가적..

공급받는 것을 집합으로 생각해서 풀어야하는 문제이므로 Union-Find를 생각해주면 된다. 추가적으로 금액이 최소인 상태로 간선들을 선택하므로 느낌이 MST와 비슷하다. 다만, 발전소를 반드시 모두 거쳐야하는 것은 아니므로 스패닝 트리는 아니다. 이 문제를 정확하게 접근해보면, 한 집합안에 발전소가 1개만 있으면 된다. 적당히 priority_queue와 Union-Find를 활용해서 풀어주면 된다. #include #include #include #include #include #include using namespace std; struct DisjointSet{ vector parent, rank; DisjointSet() : parent(1001){ for(int i = 0; i < 1001; ..

사실 아이디어는 잘 잡았는데, 구현 실력이 모자라서 시간 초과 및 메모리 초과가 나서 인터넷에서 풀이를 많이 참고하였다. 일단 처음에 들었던 생각은 다음과 같다. 문명이 몇개인지 알아야하고, 각 문명별로 컨트롤 해야하는 상황이므로 Union-Find 방법을 생각하였다. 결과적으로 그룹에 속하는지 속하지 않는지를 빠르게 판단할 수 있어야하고, 그 결합도 쉬워야하기 때문이다. (예를 들어 그룹끼리 합쳐질 때 만약 Union-Find를 사용하지 않는다면 일일히 방문하여 집합 정보에 대한 내용을 수정해주어야 하는데 이 경우에는 시간 초과가 날 수 밖에 없다.) 여기까지는 참 좋았는데, 2중 Union-Find를 진행하여 메모리 손실이 많이 발생하였다. 즉, pair parent[2001][2001]로 잡고 de..

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

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

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