200. Number of Islands (leetcode python) +DFS로 풀기

모 기업의 코딩 테스트 문제로 나왔었는데... DFS만 알면 쉽게 푸는 문제였는데 너무 아쉽다.... 알고리즘은 꾸준히 하는 게 답인 거 같다....ㅠㅠ

 

문제:

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

example 1

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

입력 값을 보면 1로 이루어진 곳이 섬이고, 0이 바다입니다. 입력 값에서 최종적으로 섬은 한 개입니다.

 

example 2

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

두 번째 케이스를 보자면  총 3개의 섬으로 이루어져 있습니다. DFS를 적용하며 풀면 쉽게 풀 수 있습니다. 상하좌우를 탐색하면서 재귀 호출하는 방법입니다.

먼저 틀을 잡아줍니다.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
    	#탐색 함수
        def dfs(i,j):

        #섬의 갯수 출력
        count =0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i,j)
                    count +=1
        return count;

DFS함수를 선언해주었습니다. 인자는 i, j값으로 배열의 위치를 받아왔습니다. 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
    	#탐색 함수
        def dfs(i,j):
            #땅이 없으면 종료
            if i<0 or i >= len(grid) or j<0 or j>=len(grid[0]) or grid[i][j] != '1':
                return
            
            #방문처리
            grid[i][j] =0
            #상하좌우 탐색
            dfs(i+1,j)
            dfs(i-1,j)
            dfs(i,j+1)
            dfs(i,j-1)

	#섬의 갯수 출력
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i,j)
                    count +=1
        return count;

DFS의 함수를 보자면 처음에 i와 j의 유효성검사를 해줍니다. 만약 유효하다면 이미 DFS 함수로 들어온 위치는 확인이 되었으니, 방문처리를 해줍니다. 구별만 해줄 수 있으면 됩니다. (아무 문자열이나 상관없습니다. 여기서는 0으로 해주었습니다.)

해당 위치에서 상하좌우를 탐색해줍니다. 탐색이 완료된 뒤 최종적으로 count값을 하나 증가시켜줍니다. 재귀로 모든 위치를 탐색하여 count값이 최종적으로 섬의 개수가 됩니다. 

 

DFS를 이해하고 문제를 풀어보니 정말 쉬운문제였습니다... 꾸준히 공부해야 할 것 같습니다.