728x90
문제
programmers.co.kr/learn/courses/30/lessons/62050
코딩테스트 연습 - 지형 이동
[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18
programmers.co.kr
테마
구현, 최소신장트리, BFS
아이디어
1. 사다리를 쓰지 않고 넘나들수 있는 영역들을 BFS로 각각 구한다.
2. 구분 영역 간에는 사다리를 놓아야 하는데, 사다리를 놓을 때의 비용이 최소인 Dictionary 을 만든다.
3. 사전을 비용 순으로 정렬한 뒤, 영역간의 최소신장트리를 만드는 크루스칼 알고리즘을 사용한다.
후기
아이디어는 그래도 잘 떠올렸지만, 어디선가 런타임에러가 발생해 애를 먹었다.
배운게 많은 문제였다.
1. defaultdict(lambda math.inf) or (lambda 0) 등을 활용해, 사전의 기본 값을 정의할 수 있다.
2. sys.setrecursionlimit(10*6) 을 통해, 기본 파이썬 재귀 제한값을 상향 조정할 수 있다.
3. 크루스칼알고리즘에서 parent 를 사전 자료형으로 선언 뒤 len(parent.values()) == 1 의 조건으로 모든 노드를 연결했는지 알 수 있다.
'프로그래밍 > programmers&bj' 카테고리의 다른 글
| [JAVA] 기능개발 (0) | 2022.02.09 |
|---|---|
| [JAVA] 완주하지 못한 선수 (0) | 2022.02.09 |
| [python] 백준 1759번: 암호 만들기 (백트래킹) (0) | 2020.10.23 |
| [python] 프로그래머스 삼각 달팽이 (0) | 2020.10.22 |
| [python] 프로그래머스 스킬트리 (0) | 2020.10.20 |