[파이썬] 프로그래머스 : 지형이동 (Lv.4)

[파이썬] 프로그래머스 :  지형이동 (Lv.4)

프로그래머스

---

풀이

0.방향성 생각

• BFS로 영역 나누기
• 한 번 더 순회하면서 다른 영역으로 갈 때 필요한 최소 cost 딕셔너리에 저장
• 모든 영역 연결해주기

1.

from collections import deque,defaultdict

def solution(land,limit):
    
    n,inf = len(land),10**9
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    
    visit = [[False]*n for _ in range(n)]
    arr = [[-1]*n for _ in range(n)]
    costs = [[[inf]*4 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for d in range(4):
                dj,di = dire[d]
                nj,ni = j+dj,i+di
                if 0<=nj<n and 0<=ni<n:
                    dh = abs(land[ni][nj]-land[i][j])
                    costs[i][j][d] = dh

• 중복 계산 줄이기 (풀고보니 없어도 푸는시간 비슷할듯)
• cost에서 다른 방향으로 가는 높이차 (cost) 저장/

2. BFS

    count = 0
    def bfs(x,y,count):
        q = deque([(x,y)])
        arr[y][x],visit[y][x] = count,True
        while q:
            x,y = q.popleft()
            for d in range(4):
                dx,dy = dire[d]
                nx,ny = x+dx,y+dy
                if 0<=nx<n and 0<=ny<n and costs[y][x][d] <= limit and not visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                    arr[ny][nx] = count
                    
    for i in range(n):
        for j in range(n):
            if not visit[i][j]:
                bfs(j,i,count)
                count += 1

• 격자 순회하면서 같은 영역에 같은 번호로 매칭해주기

3. find_parent, union 함수 정의

    table = defaultdict(lambda:inf) # table[(area1,area2)] = x 지역간 최소비용 x로 저장
    for i in range(n):
        for j in range(n):
            for d in range(4):
                dj,di = dire[d]
                nj,ni = j+dj,i+di
                if 0<=nj<n and 0<=ni<n and arr[i][j] != arr[ni][nj]:           
                    a,b,cost = arr[i][j],arr[ni][nj],costs[i][j][d]
                    table[(a,b)] = min(cost,table[(a,b)])
                    table[(b,a)] = min(cost,table[(b,a)])
    
    parent = list(range(count))
    def find_parent(a):  # MST
        if parent[a] != a:
            parent[a] = find_parent(parent[a])
        return parent[a]

    def union(a,b):  # 작은애를 부모로
        pa = find_parent(a)
        pb = find_parent(b)
        if pa != pb:
            parent[max(pa, pb)] = min(pa,pb)

• 한 번 더 순회하면서 사다리를 설치하는 경우 최소 비용을 table에 저장한다.
• table[(x,nx)] = cost : x에서 nx로 가는 최소비용은 cost

4. MST

    edges = list(table.items())
    edges.sort(key=lambda x:(-x[1]))
    
    answer = 0
    while edges:
        path,cost = edges.pop()
        x,y = path
        
        if find_parent(x) != find_parent(y):
            union(x,y)
            answer += cost
    return answer

• 비용이 제일 작은 간선부터 연결하기.
• 루프탈출 코드 넣었으면 더 빨리 끝낼 수 있었을듯.

 

---

전체코드

from collections import deque,defaultdict

def solution(land,limit):
    
    n,inf = len(land),10**9
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    
    visit = [[False]*n for _ in range(n)]
    arr = [[-1]*n for _ in range(n)]
    costs = [[[inf]*4 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for d in range(4):
                dj,di = dire[d]
                nj,ni = j+dj,i+di
                if 0<=nj<n and 0<=ni<n:
                    dh = abs(land[ni][nj]-land[i][j])
                    costs[i][j][d] = dh
                    
    def bfs(x,y,count):
        q = deque([(x,y)])
        arr[y][x],visit[y][x] = count,True
        while q:
            x,y = q.popleft()
            for d in range(4):
                dx,dy = dire[d]
                nx,ny = x+dx,y+dy
                if 0<=nx<n and 0<=ny<n and costs[y][x][d] <= limit and not visit[ny][nx]:
                    q.append((nx,ny))
                    visit[ny][nx] = True
                    arr[ny][nx] = count
    count = 0
    for i in range(n):
        for j in range(n):
            if not visit[i][j]:
                bfs(j,i,count)
                count += 1
    
    table = defaultdict(lambda:inf) # table[(area1,area2)] = x 지역간 최소비용 x로 저장
    for i in range(n):
        for j in range(n):
            for d in range(4):
                dj,di = dire[d]
                nj,ni = j+dj,i+di
                if 0<=nj<n and 0<=ni<n and arr[i][j] != arr[ni][nj]:           
                    a,b,cost = arr[i][j],arr[ni][nj],costs[i][j][d]
                    table[(a,b)] = min(cost,table[(a,b)])
                    table[(b,a)] = min(cost,table[(b,a)])
    
    parent = list(range(count))
    def find_parent(a):  # MST
        if parent[a] != a:
            parent[a] = find_parent(parent[a])
        return parent[a]

    def union(a,b):  # 작은애를 부모로
        pa = find_parent(a)
        pb = find_parent(b)
        if pa != pb:
            parent[max(pa, pb)] = min(pa,pb)

    
    edges = list(table.items())
    edges.sort(key=lambda x:(-x[1]))
    
    answer = 0
    while edges:
        path,cost = edges.pop()
        x,y = path
        
        if find_parent(x) != find_parent(y):
            union(x,y)
            answer += cost
    return answer

코멘트

.