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

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

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