성공을 즐기자

🐾 20220923 처음 DFS로 풀었다가 recursion Error로 까였다. 이렇게 생긴문제는 유니온파인드를 꼭 생각해서 풀어야겠다. 간단하게 유니온 파인드를 정리해서 포스팅 해봤다. https://what-am-i.tistory.com/371?category=1000199 [python]유니온파인드 알고리즘_이것도 알아야해? 유니온 파인드 : 노드를 UNION하고 부모를 FIND해서 서로소 집합을 찾아내는 알고리즘 UNION연산은 두 원소를 뽑아 원소가 포함된 집합의 부모노드를 비교한다. 만약 다르다면 같은 부모를 가리키도 what-am-i.tistory.com 1. 입력받은 도시의 연결 여부를 이용해 서로소 집합을 만든다. 1-2. UNION - 부모 노드를 구해 비교한다. 다르면 동일하도록 만..

유니온 파인드 : 노드를 UNION하고 부모를 FIND해서 서로소 집합을 찾아내는 알고리즘 UNION연산은 두 원소를 뽑아 원소가 포함된 집합의 부모노드를 비교한다. 만약 다르다면 같은 부모를 가리키도록 만든다. FIND 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 부모노드를 찾아 반환하게 만들면 전부 돌면서 찾아야하는 수가 있다. (시간이 너무 오래걸릴수도) 그래서 일일이 거슬러 부모노드를 찾는 것보다 한번에 빠르게 부모 노드에 갈 수 있도록 하는 경로 압축기법을 사용하면 빠르다. 코드 : def union(a,b) : a = find(a) b = find(b) if a > b : parent[a] = b elif a ..

코테에 유니온파인드가 나오나...?라는 의구심을 품고 푼 문제 유니온 파인드 문제를 처음 풀어봐서 주석을 많이 달아놨다. 이 문제를 푸는 방법은 끊을 간선을 제외한 모든 간선을 먼저 연결하고 끊을 간선들을 역순으로 하나씩 연결한다. 배열의 부모노드의 값은 음수로 집합의 개수가 저장되어있다는 것이 중요하다. 처음 배열은 -1로 초기화한다. edges,div로 연결할 리스트와 제거할 리스트를 입력받는다. 연결할 리스트의 개수만큼을 돌면서 제거될 연결이 아니라면 연결해준다.(union) answer 변수를 0으로 초기화한다. 제거할 연결을 역순으로 union한다. union은 각 집합의 개수의 곱을 반환하므로 반환값을 answer에 더한다. answer을 출력한다. ; 각 원소를 연결해주고 두 그룹의 크기의 ..