1197

알고리즘/acmicpc 2015. 6. 27. 10:53 Posted by 아는 개발자

반성해야하는 문제다

너무 문제에 성급하게 접근했다.


최소스패닝트리는 kruskal이든 prim이든 둘 중 하나를 이용해서 풀면된다.

나는 kruskal을 사용했는데 여기서 각각의 클라우드를 병합하는 과정에서 실수가 있었다.


이것은 union find라는 자료구조를 이용해서 해결해야하는데


나는 두 노드중 발견된 것들을 제외한 것만 본다고 했으니 당연히 틀릴 수밖에 없다.

(아마 이 글을 읽는 사람은 뭔말인지 모를 것이다 나만 이해할 수 있는 문장..)


프림알고리즘을 사용했으면 틀리지 않았을 것 같다...



728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

1753  (0) 2015.07.01
1795  (0) 2015.07.01
1197  (0) 2015.06.27
2268  (0) 2015.06.26
2357  (0) 2015.06.25
1138  (0) 2015.06.25