출처 : 파이썬 알고리즘 인터뷰

파이썬 알고리즘 인터뷰 책을 슬슬 1회독을 하고 있다.
사실 12월, 1월에 꾸역꾸역 거의 매일 1문제씩 풀려고 하다가 2월 되니 힘빠지고 현타와서 또 안했다...그렇게 미루고 보니 5주동안이나 손도 안댄 나.....

되게 오랫동안 안했다고 생각했는데 그래...5주만에 다시 돌아온거면 잘했어 너무 자책하지 말자 라는 마인드로 힘얻고 시작해본다.

알고리즘 책을 1회독 해도 사실 대단히 실력을 자랐다거나 하진 않았지만, 확실히 깨달은 것은

1. 내가 알고리즘을 잘 못푼다는 것
2. 머리가 그닥 좋지 못하다는 것
3. 이렇게 푸는게 아니라는 것

3가지이다.

어찌되었든 그닥 똑똑하지 못한 두뇌로 태어났기 때문에 어쩌겠나 이거 이끌고 가야된다.

그래서 DFS, BFS, Sorting, 다이나믹 프로그래밍, 그리디, 브루트포스, 백트래킹 등등 한 유형씩 다양한 문제들로 깨부수는 방식으로 1일1알고리즘 챌린지를 진행해보려 한다(혼자서).

서론이 길었다. 이제 시작.

오늘 풀어볼 문제는 leetcode 200. Number of Islands 다.

문제 요약 : mxn 행렬이 입력으로 주어지고, '1'은 땅을, '0'은 물을 의미한다. 섬의 개수는?

생각의 흐름

1이 모여있는 덩이의 개수를 세어야 하는 문제
-> 경우의 수는 '1', '0', '없음' 3가지겠구나.
-> 첫 노드([0][0])는 우, 하를 탐색.
-> 두번째 노드([0][1])는 좌, 우, 하를 탐색.
-> ...
-> [1][1]은 상,하,좌,우 를 탐색해야겠군.

=> 그래프로 접근하자

1. 그래프로 접근해서 DFS

DFS로 접근 시 탐색종료 조건 생각하기

1. grid가 끝난 경우
2. 이미 탐색한 경우 ('1'탐색완료 시 '0'으로 변경)

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' # 탐색미완료('1')-> 탐색완료('0')

상하좌우 탐색하기

dfs(i-1, j)
dfs(i+1, j)
dfs(i, j-1)
dfs(i, j+1)

2. 섬 개수 count

count = 0

첫노드부터 하나씩 for문으로 탐색

for i in range(len(grid)):
	for j in range(len(grid[0])):
    	dfs(i,j)
        count += 1
        
return count

최종 코드

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])):
            	dfs(i,j)
                count += 1
                
        return count