[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 의 조건으로 모든 노드를 연결했는지 알 수 있다.

 

 

	import math
	from collections import deque, defaultdict
	import sys
	sys.setrecursionlimit(10**6)
	def bfs(reg, land, start, height, cnt):
	dx = [0, 1, 0, -1]
	dy = [1, 0, -1, 0]
	reg[start[0]][start[1]] = cnt
	q = deque([start])
	n = len(land)
	while q:
	x, y = q.popleft()
	for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < n and 0 <= ny < n:
	h = abs(land[x][y] - land[nx][ny])
	if reg[nx][ny] == 0 and h <= height:
	reg[nx][ny] = cnt
	q.append([nx, ny])
	def find_ladder(land, region):
	dx = [0, 1, 0, -1]
	dy = [1, 0, -1, 0]
	visit = defaultdict(lambda: math.inf)
	n = len(land)
	for i in range(n):
	for j in range(n):
	for k in range(4):
	nx = i + dx[k]
	ny = j + dy[k]
	if 0 <= nx < n and 0 <= ny < n:
	if region[i][j] != region[nx][ny]:
	reg1 = region[i][j]
	reg2 = region[nx][ny]
	dif = abs(land[i][j] - land[nx][ny])
	visit[(reg1, reg2)] = min(visit[(reg1, reg2)], dif)
	return visit
	def find_parent(parent, a):
	if parent[a] != a:
	parent[a] = find_parent(parent, parent[a])
	return parent[a]
	def union_parent(parent, a, b):
	a = find_parent(parent, a)
	b = find_parent(parent, b)
	if a > b:
	parent[a] = b
	elif a < b:
	parent[b] = a
	def solution(land, height):
	answer = 0
	n = len(land)
	region = [[0] * (n) for _ in range(n)]
	cnt = 1
	for i in range(n):
	for j in range(n):
	if region[i][j] == 0:
	bfs(region, land, [i, j], height, cnt)
	cnt += 1
	visit = find_ladder(land,region)
	visit = sorted(visit.items(),key=lambda x: x[1])
	parent = {i:i for i in range(1,cnt)}
	for (x,y),val in visit:
	if find_parent(parent,x) != find_parent(parent,y):
	union_parent(parent,x,y)
	answer += val
	if len(parent.values()) == 1:
	break
	return answer

view raw 지형이동.py hosted with ❤ by GitHub