문제 설명 및 제한사항
아이디어 및 해결 방법
차근차근 생각해보면 BFS와 MST를 써서 해결 가능한 문제임을 알 수 있습니다. 아이디어를 떠올리는 순서를 요약하면
1.
사다리 없이 이동 가능한 구획들을 먼저 BFS로 파악 후 구분해봅니다. (높이 차이가 ≤ height 인 지점만 이동 가능)
2.
이제 구획 간에 사다리를 두어야 하는데, 어떤 두 구획 A와 B 사이에 사다리를 둘 수 있는 위치는 무척 많습니다. 최소 비용을 달성하려면, 그중에 어디에 사다리를 두어야 될까요? 당연히 A와 B가 인접한 위치 중 높이 차이가 가장 작은 위치가 될 것입니다.
3.
이를 활용하여 인접하고 있는 모든 구획들의 쌍에 대해 사다리를 ‘둘 수 있는’ (최소 비용의) 위치를 파악해 두고, 그 위치에 사다리를 두었을 때 발생하는 비용을 cost로 같이 저장해 둡니다.
4.
이제 이 상황은 ‘구획’들을 노드로, 사다리를 둘 수 있는 위치와 비용을 edge cost로 하는 그래프로 생각해볼 수 있고, 모든 구획들을 방문할 수 있도록 최소 비용으로 사다리를 두는 문제는 MST로 생각해볼 수 있습니다.
5.
프림 알고리즘을 써서 MST를 구현한 뒤 cost의 합을 리턴하면 됩니다.
코드
from collections import deque, defaultdict
from heapq import heappush, heappop
def solution(land, height):
R, C = len(land), len(land[0])
# bfs로 사다리 없이 이동 가능한
# 위치들의 그룹을 파악합니다
groupid, groupmap = 0, dict()
vis = set()
for r in range(R):
for c in range(C):
if (r, c) in vis:
continue
# BFS를 1회 돌립니다.
q = deque()
q.append( (r, c) )
vis.add( (r, c) )
groupmap[(r, c)] = groupid
while q:
r1, c1 = q.popleft()
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if 0 <= r1+dr < R and 0 <= c1+dc < C:
if (r1+dr, c1+dc) in vis:
continue
if abs(land[r1+dr][c1+dc] - land[r1][c1]) > height:
continue
q.append( (r1+dr, c1+dc) )
vis.add( (r1+dr, c1+dc) )
groupmap[(r1+dr, c1+dc)] = groupid
groupid += 1
# 그룹 수가 1개면 0을 리턴합니다.
if set(groupmap.values()) == 1:
return 0
# 그룹 사이의 높이 차가 최소인 지점을 edge weight로
# 둔 그래프를 하나 만듭니다.
weightmap = {}
for r in range(R):
for c in range(C):
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if 0 <= r+dr < R and 0 <= c+dc < C:
g1, g2 = groupmap[(r, c)], groupmap[(r+dr, c+dc)]
g1, g2 = min(g1, g2), max(g1, g2)
if g1 == g2:
continue
w = abs(land[r][c] - land[r+dr][c+dc])
weightmap[(g1, g2)] = min(weightmap.get((g1, g2), w), w)
G = defaultdict(list)
for (u, v), w in weightmap.items():
G[u].append((v, w))
G[v].append((u, w))
# 그룹 그래프에서 mst를 찾아 edge weight 합의
# 최솟값을 리턴하면 됩니다.
q = []
answer = 0
vis = set()
heappush(q, (0, 0))
while q:
cost, u = heappop(q)
if u in vis:
continue
vis.add(u)
answer += cost
for v, w in G[u]:
if v in vis:
continue
heappush( q, (w, v) )
return answer
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges