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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

2차원 배열의 각 좌표에 숫자 값이 적혀있고, 상하좌우로 인접한 좌표의 값의 차이에 따라 사다리를 사용하게 되는데, 사다리 이용하는 비용을 최소로 하는 방법을 구하여야 했습니다.

 

어느 한 좌표를 시작으로 하여 사다리 없이 이동이 가능한 좌표들을 모두 방문합니다.

DFS 로 탐색하는 중에 인접한 좌표와 높이 차이가 있어 사다리가 필요한 경우에, 높이 차이의 값과 인접한 좌표를 최소힙에 기록하였습니다.

 

이후 모든 좌표를 방문하지 못하였을 경우, 최소힙에서 높이 차이가 가장 적은 다음 좌표를 이용하였습니다.

다음 좌표에서도 사다리 없이 이동 가능한 모든 좌표를 방문하며, 높이 차이를 최소힙에 기록하였습니다.

2) 알고리즘

• DFS
• 최소힙

3) 풀이 코드

사용 언어 - Python

import heapq

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def solution(land, height):
    def dfs(y, x):                                                          # DFS 탐색
        nonlocal visited_cnt

        stack = [(y, x)]                                                    # 시작 좌표

        while stack:
            node = stack.pop()
            if not visited[node[0]][node[1]]:                               # 아직 방문하지 않은 좌표일때
                visited[node[0]][node[1]] = 1                               # 방문 처리
                visited_cnt += 1                                            # 방문한 좌표들 개수 카운트 추가

                for k in range(4):                                          # 상하좌우 인접 좌표
                    r = node[0] + dr[k]
                    c = node[1] + dc[k]

                    if 0 <= r < N and 0 <= c < N:
                        dif = abs(land[node[0]][node[1]] - land[r][c])      # 인접한 좌표와의 높이 차이
                        if dif <= height:                                   # 사다리 없이 이동 가능하면 스택에 좌표 추가
                            stack.append((r, c))
                        else:                                               # 사다리 필요하다면 높이 차이 값과 좌표를 최소힙에 기록
                            heapq.heappush(h, (dif, r, c))

    N = len(land)                           # 2차원 배열 길이
    answer = 0                              # 사다리 이용 비용
    visited_cnt = 0                         # 방문한 좌표 카운트

    visited = [[0] * N for _ in range(N)]   # 방문 여부 리스트
    h = [(0, 0, 0)]                         # 최소힙, 초기값은 높이 차이 0, 좌표 0,0

    while visited_cnt < N**2:               # 아직 다 방문하지 않았다면
        diff, y, x = heapq.heappop(h)       # 최소힙에서 높이 차이가 가장 작은 좌표 가져옴
        if not visited[y][x]:               # 방문하지 않은 좌표인 경우에만 탐색
            answer += diff                  # 사다리 이용 비용 추가
            dfs(y, x)

    return answer

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

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

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다