코딩테스트 연습 - 전력망을 둘로 나누기
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'study > 알고리즘' 카테고리의 다른 글
| [알고리즘/백준] Brute Force - 2309번 일곱난쟁이 / 17086번 아기상어2 (0) | 2021.12.29 |
|---|---|
| [알고리즘/프로그래머스] 퍼즐 조각 채우기 (0) | 2021.12.27 |
| [알고리즘/프로그래머스] 교점에 별 만들기 (0) | 2021.12.21 |
| [알고리즘/프로그래머스] 비밀지도 (0) | 2021.12.17 |
| [알고리즘/프로그래머스] 튜플 (0) | 2021.12.16 |
