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

전형적인 유니온-파인트(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..