복습하기7

DFS (Depth First Search) -> 스택사용이 포인트

03/19/2022

섬의개수, 전화번호 문자조합, 순열, 조합

개념을 배우고, 문제를 통해, 풀면서 익숙해지고 복습을 하는식으로 진행했는데, 지금 문제푸는것도 중요하지만 개념부터 잡는 것이 중요하다는 생각에 우선 문제보다 개념에 집중해야겠다. 당분간은, 이곳에 개념 위주로 정리를 하고, 문제는 어려운 문제 중심으로 하는게 나을것같다. 갑자기 훅 어려워지네..

섬의 개수

우선 이것을 이해하기위해서 나는 스택을 푼 문제를 보았다. 이 문제를 내 머리로 이해하는데 무려 5시간이 걸렸지만 행복하다. 드디어 알아냈다. 나는 개념이 풀리기 전까지, 앉아서 이것만 봤다. 모니터 뚫어질뻔했다. 구글에다가도 쳐보려고 했지만, 이번꺼는 일부로 안쳤다. 왜냐면 풀릴듯이 안풀렸기 때문이다. 결국엔 알아냈다. 쾌감이 어마어마하다. 이맛에 개발자되려한다. 아 행복해.
이 문제는 우선, 크게보면 세가지 아이들로 구성이된다. 첫번째는 한칸한칸 옆으로 이동해주는 아이, 동서남북으로 1이 보이면 0으로 바꿔주주는 아이 (그래야 시간을 효율적으로 복잡도를 낮춰주고, 귀찮게 문제를 풀때 귀찮게 안해도 된다), 세번째는 섬의 개수가 몇개인지 카운터해주는 주머니역할!
아무튼 이 세개로 이루어져있는데, 여기서 내가 시간이 오래걸린 이유는 중첩for문이 사용되었기 때문이다. 그렇기때문에 이것을 눈으로 왔다갔다 시간도 오래걸렸다. 아무튼 내가보았을때 이 문제만 알면 오늘하루 나머지 문제들은 끝날것같다. 이제 이해한 것을 바탕으로 구현연습을 하러 가보려고 한다.

#stack으로 풀기
def island_dfs_stack(grid): #그리드가 들어왔을때
    #탐색범위를 한정, 상대적인 x좌표와 y좌표
    dx = [0, 0, 1, -1] #행 (가로) 좌우
    dy = [1, -1, 0, 0] #열 (세로) 상하
    rows, cols = len(grid), len(grid[0]) #여기다가 저장하고
    cnt = 0

    for row in range(rows): #이중 for문 돈다.
        for col in range(cols):
            if grid[row][col] != '1':#내가 방문한곳이 1인지 아닌지 확인한다. 1인곳만 방문한다
                continue

            cnt += 1 #섬의 숫자를 올린다.
            stack = [(row, col)] #점의 좌표를 스택에 넣는다.

            while stack:
                x, y = stack.pop()
                grid[x][y] = '0'
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    stack.append((nx, ny))
    return cnt


assert island_dfs_stack(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_dfs_stack(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 3
grid = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]
# print(len(grid[0]))
print(island_dfs_stack(grid))

사실 스택으로 하는 방법보다는 재귀로 하는 방법이 더 직관적이고 헷갈리지 않는다. 하지만 스택으로 개념을 이해하려고 고집을 피운 이유는, 이렇게 구현해보고 싶었기 때문에 코드 하나하나 집중해보았다.

다음은 재귀를 사용하여 푼 것이다.

#recursive
def island_dfs_recursive(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    m = len(grid)
    n = len(grid[0])
    cnt = 0

    def dfs_recursive(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return

        # 방문처리
        grid[r][c] = '0'
        for i in range(4):
            dfs_recursive(r + dx[i], c + dy[i])
        return

    for r in range(m):
        for c in range(n):
            node = grid[r][c]
            if node != '1':
                continue

            cnt += 1
            dfs_recursive(r, c)

    return cnt


assert island_dfs_recursive(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_dfs_recursive(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

BFS (Breadth First Search) -> 큐사용이 포인트

섬의개수 BFS버전

그냥 단순히 스택을 큐로 바꾸는 정도이다..

def island_bfs(grid):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != '1':
                continue

            cnt += 1
            q = deque([(row, col)])

            while q:
                x, y = q.popleft()
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != '1':
                        continue
                    grid[nx][ny] = '0'
                    q.append((nx, ny))
    return cnt


assert island_bfs(grid=[
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]) == 1
assert island_bfs(grid=[
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]) == 3

한문제 한문제 유심히 관찰하고 생각하는게 중요한것같다. 마치 헬스할때, 무거운것을 들으려고 팔이 파르르 떨리면서 힘들게힘들게 들어올린 느낌이랄까. 쉽지않다. 하지만, 재밌다. 그리고 DFS와 BFS관련 문제들은 다 비슷비슷 한것같다. 특정한 보이지않는 공식같은게 있다. 아직 많이 풀어보지 않아서 감이 잘 오질 않는데, 이상하게 촉이 발동한다. 비슷비슷한 그런 느낌? 무슨말인지알지? 물론 알고리즘은 생각해서 하는거긴한데, 일단 많이 풀어보고 머리에 DFS와 BFS를 풀때 어떻게 풀어나가야하는지 패턴화하고 알아야한다는 말이다.