[백준] Watering the Fields : 10021 Python

핑계지만 한동안 프로젝트를 진행한다고 알고리즘 문제를 풀지 못하였다. 아무래도 처음 진행해보는 프로젝트이다 보니 하루에 어느 정도 해야지라는 양을 가늠하지 못하고, 시간이 있을 때마다 프로젝트에 몰두한다고 나의 다른 스케줄을 잘 진행하지 못한 것 같다. 앞으로 프로젝트를 할 때는 프로젝트도 중요하지만 시간 배분을 조금 더 유동적으로 해봐야겠다.

문제 얘기를 해보자면 이번에 푼 문제는 Watering the Fields이다. 문제가 영어버전 밖에 없지만, 다행히 문제 길이도 길지 않고, 문제에서 하는 얘기도 딱 보이기 때문에 영어가 약한 나에게도 해석상에 큰 문제는 없었다.

문제 줄거리는 농부가 물을 받아놓기 위해 파이프를 연결해놓아야 한다는 내용이지만, 결국에는 문제에서 모든 파이프의 좌표가 주어지고, 각 파이프 사이의 유클리디안 거리의 제곱((xi - xj)^2 + (yi - yj)^2)이 비용이 될 때, 모든 비용이 C보다 큰 최소 비용을 구하는 문제이다.

조금 더 정리해서 말하자면, MST(최소신장트리)를 구하는데 각 거리는 C보다 큰 최소 신장 트리를 구하라는 문제이다.

나는 이 문제를 보고 저번에 풀었던 SWEA 하나로문제에 Prim알고리즘을 조금 변형해서 풀면 되겠다!라는 생각으로 문제를 접근하였다. 사실 하나로 문제풀이에서도 적었었는데, 아직 Prim알고리즘이 왜 mst가 되는지는 아직 이해하지 못했지만 이 문제를 풀면서 프림 알고리즘 방식에 대해서는 확실히 이해할 수 있었던 것 같다.

추가로, 이 문제역시 백준 문제답게 시간제한이 1초이다. 문제를 풀면서 계속 이렇게 풀면 1초가 가능할까? 이중 포문 (2000 * 2000) 한번 써도 시간 초과가 날 거 같은데? 고민하며 문제를 풀었다. 이 과정에서 굳이 가중치를 닮아놓을 2차원 배열이 필요할까?(물론 2차원 배열을 사용하는 것이 더 시간이 걸린다는 확신은 없었다), 하나로 문제풀이처럼 자신의 부모 노드의 대한 정보가 필요할까? 고민하다가 한번 이 두 가지 없이 문제를 풀어보았다.

내가 생각한 아이디어로 프림알고리즘을 시도해본다면,
1. 첫번째 for문에서는 활성화된 모든 도착지점 중 최소거리인 곳(아직 방문하지 않은 곳)을 방문한다, 활성화된 최소 거리가 없다면 -1을 반환한다
2. 위과정에서 첫 번째 시도는 당연히 활성화된 도착지점이 없기 때문에 -1을 반환하지 않고 방문 체크를 하고 넘어간다
3. 방문체크를 한 기점에서 각 노드들 까리의 거리를 다시 구하며, C보다 크고, 이전에 구한 거리(비용) 보다 작다면 최신화 및
도착지점을 활성화 한다.

이렇게 모든 실행을 다한다면 최소 도착거리가 구해진다. 이것을 코드로 본다면 아래와 같이 된다.

Watering the field 정답코드

변수에 대한 설명을 잠깐 하자면 D는 다익스트라와 유사하게 방문 체크되지 않은 인덱스면 꾸준히 거리를 최솟값(C보다는 큰) 값으로 활성화해주며 최소거리로 mst에 이어지게 만들어주는 변수이다.

다행히 바로 python과  pypy 모두 문제를 통과할 수 있었고, 나쁘지 않은 성능을 보이는 코드를 완성시킨 것 같다.

오랜만에 푼 문제였는데 난이도가 꽤 있는 문제임에도 불구하고 비교적 쉽게 풀려서 매우 기분이 좋았다. 프로젝트도 끝났겠다 알고리즘 파이팅이다!