Graph

Number of Islands

이 문제는 크게 2가지 흐름으로 처리한다.

 

첫 번째는 grid의 모든 cell을 scan 하면서 땅(1)을 찾는 것이다.

 

그리고 땅이 나오면 인접한 땅이 있는지를 확인하고 해당 땅이 속한 섬을 확인한다.

아래 좀 더 자세하게 설명한다.

먼저 땅을 발견하면 확인한 땅이라고 체크를 하기 위해 해당 cell의 값을 2로 변경한다.

그리고 해당 cell과 인접한 cell에 땅이 있는지를 확인한다.

 

이를 상좌하우 순으로 확인한다고하면

위쪽 cell은 grid 범위를 벗어나고, 왼쪽 cell은 땅이 아니다.

 

아래 cell은 땅이므로 해당 cell을 확인된 땅이라고 체크한다.

 

그리고 새로 확인된 땅이라고 체크해놓은 cell 인접

해당 cell의 윗 cell은 확인된 땅이므로 다시 작업을 하지않는다.

 

이렇게 재귀적으로 인접한 cell이 땅임을 확인하고 체크하여 하나의 섬을 체크한다.

결과적으로 위와 같이 하나의 섬이 생긴다.

 

이렇게 하나의 섬을 확인한 후에는 다시 전체 cell을 scan하면서 확인되지 않은 땅을 확인하고,

해당 땅을 기준으로 섬을 확인하는 식으로 진행한다.

 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nums = 0

        for y in range(len(grid)):
            for x in range(len(grid[0])):

                if grid[y][x] == "1":
                    nums += 1
                    self.check(grid, x, y)

        return nums

    def check(self, grid, x, y):
        grid[y][x] = "2"

        # 상
        if (0 < y) and (grid[y - 1][x] == "1"):
            self.check(grid, x, y - 1)

        # 좌
        if (0 < x) and (grid[y][x - 1] == "1"):
            self.check(grid, x - 1, y)

        # 하
        if (y < len(grid) - 1) and grid[y + 1][x] == "1":
            self.check(grid, x, y + 1)

        # 우
        if (x < len(grid[0]) - 1) and grid[y][x + 1] == "1":
            self.check(grid, x + 1, y)

 

Letter Combinations of a Phone Number

 

 

첫 번째 숫자에 대한 문자들을 하나 씩 iterating 한다. 이때 문자를 letter1 이라 한다.

만약 입력의 숫자(digits)가 1자리 이면 letter1 을 결과에 포함한다. 

 

두 번째 숫자에 대한 문자들을 하나 씩 iterating 한다. 이때 문자를 letter2 이라 한다.

만약 입력의 숫자(digits)가 2자리 이면 letter1 + letter2 를 결과에 포함한다.

 

세 번째 숫자에 대한 문자들을 하나 씩 iterating 한다. 이때 문자를 letter3 이라 한다.

만약 입력의 숫자(digits)가 3자리 이면 letter1 + letter2 + letter3 를 결과에 포함한다.

 

...

 

class Solution:
    keyboard = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        def append_letter(index: int, combination: str):
            if len(combination) == len(digits):
                result.append(combination)
                return

            digit = digits[index]
            for letter in self.keyboard[digit]:
                append_letter(index + 1, combination + letter)

        result = []
        append_letter(0, "")
        return result