[1스4코2파] # 223 LeetCode 200. Number of Islands

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (223차)
[4코1파] 2023.01.13~ (215일차)
[1스4코1파] 2023.04.12~ (126일차)
[1스4코2파] 2023.05.03 ~ (104일차)

Today :

2023.08.15 [223일차]
graph
https://leetcode.com/problems/number-of-islands/

200. Number of Islands

https://leetcode.com/problems/number-of-islands/

문제 설명

M x N 형태의 2차원의 이진 그리드가 주어질때, 그리드 내의 요소 1은 섬, 0은 물로 이루어져 있는 섬을 나타낸다.
섬은 물로 둘러쌓여 있고 인접한 육지를 수평 혹은 수직으로 연결하여 형성된다. 그리드의 네 모서리가 모두 물로 쌓여 있는 것을 섬이라고 할 때, 섬의 개수를 return

문제 풀이 방법

graph 문제이지만 dfs 혹은 bfs로 푸는 문제
bfs는 queue를 이용해서, recursive 하게 푼다.
bfs는 섬일 조건을 만족하는 좌표를 queue에 넣고 +1 하는 방식으로
진행하고, dfs는 섬의 조건을 만족하지 않는(물인 조건)을 base로 해서 dfs 조건을 끊어버리는 recursive 한 과정으로 푼다.

내 코드

bfs 알고리즘으로 queue를 이용해서 푼 것

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0 
    
        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0

        def bfs(r,c):
            queue = collections.deque()
            queue.append((r,c))
            visited.add((r,c))
            directions = [[1,0], [-1,0], [0,1], [0,-1]]

            while queue:
                r,c = queue.popleft()
                for x, y in directions:
                    dr, dc = r+x, c+y
                    if dr in range(rows) and dc in range(cols) and grid[dr][dc] == '1' and (dr, dc) not in visited:
                        queue.append((dr,dc))
                        visited.add((dr,dc))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and (r,c) not in visited:
                    bfs(r,c)
                    islands +=1
        
        return islands
        

dfs를 이용해서 recursive 하게 풀기

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0
        directions = [(1,0),(-1,0),(0,1),(0,-1)]

        def dfs(r,c):
            if r not in range(rows) or c not in range(cols) or grid[r][c]=='0' or (r,c) in visited:
                return
            visited.add((r,c))
            for x,y in directions:
                dfs(r+x, c+y)
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c]=='1' and (r,c) not in visited:
                    dfs(r,c)
                    islands +=1
                    
        return islands

증빙

여담

왜 내일 출근이지