1944번 - 복제 로봇
1. S 또는 K에서만 로봇 복제가 가능하다는 것이 어떤 의미인지 더 고민해볼 필요가 있습니다. 곰곰히 생각해보면 정점과 정점을 연결하는 최소 비용을 구하는 문제로
사실 로봇이 어디서 복제되는지는 중요한 정보가 아닙니다. 결국 어떤 정점 (S or K)에서 다른 정점으로 이어지는 최소 거리를 찾는 것이 핵심입니다.
이 때, 모든 정점(시작점으로 부터 모든 열쇠를 방문)이 연결되는 최소 비용을 찾아야 하므로 자연스럽게 MST (최소 신장 트리)로 이어집니다.
2. 2차원 배열에서 최소 신장 트리를 어떻게 구하느냐? 우선 정점 사이의 최단 거리를 구하고 인접 배열이나 인접 리스트로 표현해야 합니다.
각 정점과 정점 사이의 최단 거리를 구해야하므로 각 정점에 대해서 bfs 탐색을 진행할 수 있습니다.
최악의 경우 그리드 크기는 50 x 50 = 2500칸이고 정점의 최대 개수는 250개 이므로
2500 x 250 = 625,000 번안에 각 정점 사이의 최단 거리를 모두 구할 수 있습니다.
3. 이후 결정된 정점 사이의 최단 거리를 이용해 MST 를 구하면 됩니다.
이 때, 그래프의 밀도에 따라서 인접 배열O(V²)과 인접 리스트 O(E log V) 를 선택해주시면 됩니다.
해당 문제에서는 어떤 방식을 사용하던 시간 복잡도에 걸리지 않습니다.
댓글을 작성하려면 로그인해야 합니다.
potential1205 1년 전
1. S 또는 K에서만 로봇 복제가 가능하다는 것이 어떤 의미인지 더 고민해볼 필요가 있습니다. 곰곰히 생각해보면 정점과 정점을 연결하는 최소 비용을 구하는 문제로
사실 로봇이 어디서 복제되는지는 중요한 정보가 아닙니다. 결국 어떤 정점 (S or K)에서 다른 정점으로 이어지는 최소 거리를 찾는 것이 핵심입니다.
이 때, 모든 정점(시작점으로 부터 모든 열쇠를 방문)이 연결되는 최소 비용을 찾아야 하므로 자연스럽게 MST (최소 신장 트리)로 이어집니다.
2. 2차원 배열에서 최소 신장 트리를 어떻게 구하느냐? 우선 정점 사이의 최단 거리를 구하고 인접 배열이나 인접 리스트로 표현해야 합니다.
각 정점과 정점 사이의 최단 거리를 구해야하므로 각 정점에 대해서 bfs 탐색을 진행할 수 있습니다.
최악의 경우 그리드 크기는 50 x 50 = 2500칸이고 정점의 최대 개수는 250개 이므로
2500 x 250 = 625,000 번안에 각 정점 사이의 최단 거리를 모두 구할 수 있습니다.
3. 이후 결정된 정점 사이의 최단 거리를 이용해 MST 를 구하면 됩니다.
이 때, 그래프의 밀도에 따라서 인접 배열O(V²)과 인접 리스트 O(E log V) 를 선택해주시면 됩니다.
해당 문제에서는 어떤 방식을 사용하던 시간 복잡도에 걸리지 않습니다.