22287번 - Mr. Plow King
제가 풀어본 문제 중에 가장 이해가 안 되었던 문제 중에 하나였는데, 저도 구글링으로 겨우 정보를 찾아서 다른 분들 이해에 도움이 되고자 조금 적어 봅니다.
문제를 해결하기 위해 n개의 도시에 있는 1 .. m의 도로 중에 n - 1 개의 도로을 선택해야 합니다.
이때 가장 가치가 큰 도로만 선택할 수 있는 것이 아니라 작은 도로부터 선택해야 합니다.
다만 선택할 수 있는 도로의 가치를 높이기 위해서 최대한 사이클을 구성해 가며 선택할 수 있는 작은 가치의 도로를 없애 나가야 합니다.
이를테면 입력 에시에 있는 6 8의 경우를 설명 드리면
가장 먼저 1번 도로를 선택합니다.
두 번째로 2번 도로를 선택합니다.
3번 도로를 1 2 번 도로에 연결된 도시를 연결해서 사이클을 구성합니다. 이렇게 되면 MST 가 될 수 없기 때문에 3번 도로는 선택할 수 없습니다.
세 번째로 4번 도로를 선택합니다.
5번 도로와 6번 도로 또한 3번 도로와 마찬가지로 사이클을 구성하게 연결할 수 있기 때문에 선택하지 않을 수 있습니다.
그럼 3개의 도로가 선택되어 2개를 더 선택해야 되고 남은 도로가 7, 8번 도로 밖에 없기 때문에 해당 도로를 선택합니다.
그럼 1 + 2 + 4 + 7 + 8 번 도로가 선택되어서 정답이 22가 나오는 것입니다.
댓글을 작성하려면 로그인해야 합니다.
loveisasong 1년 전
제가 풀어본 문제 중에 가장 이해가 안 되었던 문제 중에 하나였는데, 저도 구글링으로 겨우 정보를 찾아서 다른 분들 이해에 도움이 되고자 조금 적어 봅니다.
문제를 해결하기 위해 n개의 도시에 있는 1 .. m의 도로 중에 n - 1 개의 도로을 선택해야 합니다.
이때 가장 가치가 큰 도로만 선택할 수 있는 것이 아니라 작은 도로부터 선택해야 합니다.
다만 선택할 수 있는 도로의 가치를 높이기 위해서 최대한 사이클을 구성해 가며 선택할 수 있는 작은 가치의 도로를 없애 나가야 합니다.
이를테면 입력 에시에 있는 6 8의 경우를 설명 드리면
가장 먼저 1번 도로를 선택합니다.
두 번째로 2번 도로를 선택합니다.
3번 도로를 1 2 번 도로에 연결된 도시를 연결해서 사이클을 구성합니다. 이렇게 되면 MST 가 될 수 없기 때문에 3번 도로는 선택할 수 없습니다.
세 번째로 4번 도로를 선택합니다.
5번 도로와 6번 도로 또한 3번 도로와 마찬가지로 사이클을 구성하게 연결할 수 있기 때문에 선택하지 않을 수 있습니다.
그럼 3개의 도로가 선택되어 2개를 더 선택해야 되고 남은 도로가 7, 8번 도로 밖에 없기 때문에 해당 도로를 선택합니다.
그럼 1 + 2 + 4 + 7 + 8 번 도로가 선택되어서 정답이 22가 나오는 것입니다.