서로소집합

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 유형에는 완전탐색이라고 되어 있기하던데 난 다른 방식으로 풀었다.n개의 송전탑이 하나의 트리 형태로 연결되어 있고, 그 중 하나의 전선을 끊어 두 개의 트리로 만든다.그리고 각 트리에서의 원소 개수 차이가 최소가 되는 그 최소값을 구하면 된다. union-find를 통해서 풀었다.반복문을 통해 각 전선을 하나씩 제거하면서 union-find연산을 통해 각 송전탑들이 속하고 있는 트리를 저장한다.그리고 각 경우에 대해, 트리에 속한 송전탑의 개수 차이가 최솟값인 경우를 갱신해서 리턴한다. 풀이 코드from coll..
happenundo
'서로소집합' 태그의 글 목록