본문 바로가기

study/알고리즘

[알고리즘/프로그래머스] 전력망을 둘로 나누기

위클리 챌린지 > 전력망을 둘로 나누기

 

코딩테스트 연습 - 전력망을 둘로 나누기

9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1

programmers.co.kr

 

나의 풀이

 

- BFS 사용해서 끊을 수 있는 모든 경우의 수를 구해 가장 작은 값을 구한다.

 

- 시간이 오래 걸리는 것 같다.

 

다른사람의 풀이

 

- Union find (disjoint-set) 사용 -- 공부 필요

- defaultdict로 처음 dict 초기화

: 빈 딕셔너리는 미리 삽입하지 않은 key를 호출하면 에러 발생 --> 이를 방지해줌

from collections import defaultdict