경로압축

[백준] 4195 친구 네트워크 | Union Find, 경로압축 | Gol2 Pythonhttps://www.acmicpc.net/problem/4195  접근유형 : union find (합집합)union find 인데 노드 이름이 문자열인union find 짤 때 모든 연산은 루트노드 기준으로 할 것 기억하기..~! [문제 해석]sns 친구추가(합집합 연산) 시마다 그 새로운 친구 네트워크에 포함된 전체 친구 수 구하기친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말함친구 = 노드, 친구관계 = 간선시간제한 3초친구관계 수 앗.. 사이클이 생길수도 있겠네..? 같은 네트워크면 친구추가 무시해야겠다노드가 친구이름으로 주어지니까 딕셔너리를 쓰자 구상 : 노드이름 문자열에 해당하는 번호를 따로 ..

[백준] 1717 집합의 표현 | Union Find, 경로압축 | Gol5 Pythonhttps://www.acmicpc.net/problem/1717 구상유형 : union find +경로압축둘 다 새롭게 구현해본 개념이라 공부가 많이 됐다!union find만으로는 시간초과가 나서 경로압축 등 find함수를 최적화하여 해결했다.새로운 재미가 있던 문제~ [문제 해셕]0~n 각 하나씩만 원소로 갖는 집합 n+1개가 주어지고, 이들 간의 집합 연산 결과 출력하기0 a b : a와 b가 포함되어있는 집합의 합집합 연산1 a b : a와 b가 같은 집합의 원소인지 확인하는 연산a = b 일 수도 있음1 1 시간제한 : 2초 트러블 슈팅TS 1 : 합집합 연산 시 x,y가 포함된 집합 전체를 연결시켜야하므로..