[TIL_Carrotww] 96 - 23/02/03

📝Carrotww의 코딩 기록장

🧲 python algorithm dfs 1

🔍 Leetcode 200 Number of Islands - Medium

dfs 기본 풀이라고 볼 수 있다.
dfs 문제를 풀어봤다면 쉽게 풀 수 있다.
방향을 정해줄 dx, dy 리스트를 만들어 주고 방문 처리를 해줄 visited와 좌표를 저장해줄
stack을 선언 후 방문처리를 해가며 이어져있는 섬의 개수를 찾으면 된다.

• 풀이

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        result = 0
        visited = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]

        def dfs(x, y):
            if visited[x][y] == 1 or grid[x][y] == '0':
                return 0

            stack = [(x, y)]
            visited[x][y] = 1
            while stack:
                x, y = stack.pop()
                for i in range(4):
                    n_x, n_y = x + dx[i], y + dy[i]
                    if n_x >= 0 and n_x < len(grid) and n_y >= 0 and n_y < len(grid[0]):
                        if visited[n_x][n_y] == 0 and grid[n_x][n_y] == '1':
                            visited[n_x][n_y] = 1
                            stack.append((n_x, n_y))
            return 1

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

        return result

🧲 python algorithm dfs 2

🔍 Leetcode 130 Surrounded Regions - Medium

위와 비슷한 방식으로 풀면 된다.
문제를 초반에 조금 잘못 이해해서 코드를 수정하느라 조금 시간이 걸렸지만 이정도면 간단한 편에 속한다.

• 풀이

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        visited = [[0 for _ in range(len(board[0]))] for _ in range(len(board))]
        stack = []
        dx, dy = [0, 0, -1, 1], [1, -1, 0, 0]

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "O" and visited[i][j] == 0:
                    temp = []
                    stack.append((i, j))
                    temp.append((i, j))
                    change = 1
                    while stack:
                        x, y = stack.pop()
                        visited[x][y] = 1
                        for di in range(4):
                            n_x, n_y = x+dx[di], y+dy[di]
                            if (n_x < 0 or n_x >= len(board)) or (n_y < 0 or n_y >= len(board[0])):
                                change = 0
                                continue
                            if visited[n_x][n_y] == 0 and board[n_x][n_y] == "O":
                                stack.append((n_x, n_y))
                                temp.append((n_x, n_y))
                    if change == 1:
                        for te in temp:
                            board[te[0]][te[1]] = "X"

        return board

속도가 빠르게 나오지 않아 찾아보니 X 안에 갇힌 O를 찾으면 되는 문제이기 때문에
좌표의 겉부분을 돌며 체크하는 방법으로 푸는 방식이 있었다.
전혀 생각하지 못했는데 그렇게 푸는게 확실히 문제를 잘 이해한 풀이라고 생각된다.
나중에 다시 풀어서 올려봐야겠다.