ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1197
    알고리즘/acmicpc 2015. 6. 27. 10:53

    반성해야하는 문제다

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


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

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


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


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

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


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



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

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

    댓글

Designed by Tistory.