[Python] 프로그래머스 지형 이동

문제

programmers.co.kr/learn/courses/30/lessons/62050

코딩테스트 연습 - 지형 이동

 

테마

구현, 최소신장트리, 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 의 조건으로 모든 노드를 연결했는지 알 수 있다.