[노씨데브 킬링캠프] 3주차 - 문제풀이 : Number of Islands

Number of Islands - LeetCode

접근 방법 [필수 작성]

제한 조건 확인

• 300300 → 90000 네가지 방향 → 9만 4 → 36만
• 완탐해도 시간 문제 없음

아이디어

dfs 던, bfs 던 뭐로 구현하던 상관없을듯

bfs, queue 로 빠르게 구현

어떻게 같은땅인지 다른 땅인지 구분할 것인가?

1이 나오면 한번도 방문안했던 1이라면, count 를 1증가 시키고 해당 1과 연결되어있는 모든 1들을 방문한 1로 변경

시간복잡도

자료구조

코드 구현 [필수 작성]

1차 시도 (소요시간 25분)

nonlocal 을 너무 남발하는 느낌인데,

어떻게 지워볼 수는 없을까?

→ 위험한 사용은 아니라, 딱히 크게 상관없을 것 같다.

from collections import deque

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        columns = len(grid[0])
        visited = [[False]*columns for _ in range(rows)]
        count = 0

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

        def is_valid_land(r,c):
            nonlocal grid
            nonlocal rows
            nonlocal columns
            nonlocal visited

            if 0 <= r < rows and 0 <= c < columns:
                if visited[r][c] == False:
                    if grid[r][c] == "1":
                        return True
            return False

        def bfs(input_r,input_c):
            nonlocal dr
            nonlocal dc

            queue = deque([(input_r,input_c)])
            while queue:
                r,c = queue.popleft()
                for i in range(4):
                    nr = r + dr[i]
                    nc = c + dc[i]
                    if is_valid_land(nr,nc):
                        visited[nr][nc] = True
                        queue.append((nr,nc))

        for r in range(rows):
            for c in range(columns):
                #print("r=",r,"  c=",c)
                if is_valid_land(r,c):
                    #print("r=",r,"  c=",c, "is valide land")
                    visited[r][c] = True
                    count += 1
                    bfs(r,c)

        return count

배우게 된 점 [ 필수 X ]

자유 형식

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

수고하셨습니다!