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

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

문제

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

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

코드

이 문제는 최근에 풀었던 알고리즘 문제중에서 가장 어려웠던것같다.

우선 가장 처음에 문제에 접근할때

1. 사다리 없이 이동 가능한 그룹끼리 그룹을 생성
2. 현재 자리의 4방향을 탐색하면서 나와 다른 그룹을 경우 높이차를 측정
3. 최소 높이차를 측정하여 결과를 구함

이 과정을 생각하고 풀어나갔는데 2번에서 시간 복잡도와 테스트케이스에서 계속 틀리면서 문제가 발생하면서 어려움을 겪었다.

결국 과거 풀던 문제를 복기하던중에 섬을 이동하면서 최소의 거리를 구하는 문제에서 mst를 통한 문제해결을 떠올렸고, mst를 통해 겨우 풀수 있었다.

1. 사다리 없이 이동 가능한 그룹끼리 그룹을 생성
2. 각각의 그룹에서 다른그룹을 가기 위한 가중치를 모두 구함
3. MST 자료구조를 통해 가중치를 갱신해나가면서 최소가중치를 구함

import heapq
dx = [-1,1,0,0]
dy = [0,0,1,-1]
# 1. 그룹 생성
def BFS(x,y,n,land,height):
    q = []
    visited = [[0]*n for _ in range(n)]
    var = 0
    tmp = []
    tmp.append([x,y])
    while tmp:
        i,j = tmp.pop(0)
        if visited[i][j] != 0:
            continue
        var += 1
        visited[i][j] = var
        q.append([i,j])
        while q:
            x,y = q.pop(0)
            for k in range(4):
                nx = x + dx[k]; ny = y + dy[k]
                if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
                    cur_next_diff = abs(land[nx][ny] - land[x][y])  # 현재위치와 다음위치의 차이
                    if cur_next_diff <= height:
                        visited[nx][ny] = var
                        q.append([nx,ny])
                    else:
                        tmp.append([nx,ny])
    return visited, var
# 2. MST를 위한 인접리스트 생성
def mst_make(visited, land, n, var):
    adj = { i : [] for i in range(1,var+1)}
    for i in range(n):
        for j in range(n):
            cur = visited[i][j]
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if 0 <= nx < n and 0 <= ny < n:
                    next = visited[nx][ny]
                    if cur < next:
                        adj[cur].append([abs(land[nx][ny] - land[i][j]),next])
                        adj[next].append([abs(land[nx][ny] - land[i][j]), cur])
    return adj

# 3. 가중치를 갱신해나가면서 최소가중치합을 찾는다
def MST(adj,var):
    # print(adj)
    INF = float('inf')
    weight = [INF]*(var+1)
    mst = [False] *(var+1)
    pq = []
    weight[1] = 0
    heapq.heappush(pq,(0,1))    # 가중치, 위치
    res = 0
    while pq:
        w, node = heapq.heappop(pq)
        if mst[node]:
            continue
        mst[node] = True
        res += w
        for w, next_node in adj[node]:
            if not mst[next_node] and weight[next_node] > w:
                weight[next_node] = w
                heapq.heappush(pq, (weight[next_node], next_node))
    return res

def solution(land, height):
    n = len(land[0])
    visited, var = BFS(0,0,n,land,height)
    adj = mst_make(visited, land, n ,var)
    res = MST(adj,var)
    return res