(Python3) - LeetCode (Medium) : 1765. Map of Highest Peak

https://leetcode.com/problems/map-of-highest-peak

bfs로 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

다음 변수를 선언합니다.

📑 행 길이 rowLength

📑 열 길이 colLength

📑 인접 방향을 탐색할 배열 dr, dc 및 deque dq

📑 순회를 마쳤을 때 배열 정답 변수 grid, 방문여부 ck

📔 풀이과정

📑 water인 지점에서 얼만큼 떨어져 있는지의 거리가 높이와 같으므로 bfs로 해결가능합니다. bfs함수를 구현합니다.

📑 isWater를 이차원으로 순회하며 물인 지점을 먼저 방문하며 각 행,열을 먼저 순회하기 위해 dq에 append합니다.

📑 dq에 대해 순회하며 인접한 좌표를 확인하며 범위를 넘지 않으며 방문하지 않았다면 이전 거리에서 1을 증가시킨 값을 저장합니다.

 

📑 시간 복잡도

각 행과 열이 각각 1000, 1000까지이므로 100만의 배열공간을 차지하며 각 좌표를 한번씩 순회하므로 O(100만)으로 해결가능합니다. 

📑 공간 복잡도

각 행과 열이 각각 1000, 1000까지이므로 100만의 배열공간을 차지하며

📔 정답 출력 | 반환

순회 결과 높이들이 저장된 grid를 반환합니다.

---

📕 Code

📔 Python3

from collections import deque
class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        rowLength = len(isWater)
        colLength = len(isWater[0])

        def bfs():
            dr = [0,0,1,-1]
            dc = [1,-1,0,0]
            dq = deque()
            grid = [[0 for _ in range(colLength)] for _ in range(rowLength)]
            ck = [[0 for _ in range(colLength)] for _ in range(rowLength)]

            for i in range(rowLength):
                for j in range(colLength):
                    if isWater[i][j] == 1:
                        dq.append((i,j))
                        ck[i][j] = 1
                        
            while dq:
                r, c = dq.popleft()
                for i in range(4):
                    nr = r + dr[i]
                    nc = c + dc[i]
                    if not 0 <= nr < rowLength or not 0 <= nc < colLength:
                        continue
                    if ck[nr][nc] == 1:
                        continue
                    grid[nr][nc] = grid[r][c] + 1
                    ck[nr][nc] = 1
                    dq.append((nr,nc))
            
            return grid

        return bfs()

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.