유니온파인드
-
(백준 16562번 친구비 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 3PROGRAMMING/C++ 2024. 5. 9. 21:23
백준 16562번https://www.acmicpc.net/problem/16562 유니온 파인드 문제인 걸 알고봐서 아이디어를 내는 건 어렵지 않았다.연결된 그래프 중 가장 친구비가 작은 노드를 root node로 지정하고, root node들을 다 더한 값이 이준석 학생이 가진 돈보다 많으면 된다도 생각했다. 고런데,,,!! 29%에서 안되는 것이 아닌가! 그래서 찾은 문제점 1. 일단 반례부터 투척(출처) : https://www.acmicpc.net/board/view/81875반례 :5 3 2010 20 20 10 301 32 45 4답 : 20 node의 번호와 node의 value는 다르다. 1번이라고 해서 무조건 작은 친구비를 갖는게 아님!!!! 위 반례를 통해 그 부분을 수정할 수 있..
-
(백준 1976번 여행 가자 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 2PROGRAMMING/알고리즘 2024. 5. 9. 20:07
(노느라) 바쁘다는 핑계로 공부를 소홀히 하는 것 같아 마음이 불편하다.이제는 진짜 매일 1백준 해야겠다!!! 백준 1976번https://www.acmicpc.net/problem/1976 이 문제는 Union Find 라고 해서 봤는데 처음에는 뭔 소리인가 했다. dfs로 풀어야 하나 생각하고 있었는데!Union Find로 아이디어를 틀었다. 이디야에서 샤인히비스커스를 마시면서 깨달은 사실 : 사실 어떤 도시를 몇 번 가는지는 중요하지 않다! 연결된 도시는 무조건 방문이 가능하다. 이 말인 즉, 여행을 가고지 하는 도시들이 하나의 connected graph의 node들이기만 하면 된다는 의미!그리고 하나의 connected graph에 속하는지 아닌지는 root node가 동일한지 아닌지만 확인하..