[1스4코2파] #131. LeetCode Algorithm Day 7 (733. Flood Fill, 695. Max Area of Island)

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (131일차)
[4코1파] 2023.01.13~ (122일차)
[1스4코1파] 2023.04.12~ (33일차)
[1스4코2파] 2023.05.03 ~ (12일차)

Today :

2023.05.14 [131일차]

LeetCode Algorithm Day 7
733. Flood Fill

• https://leetcode.com/problems/flood-fill/?envType=study-plan&id=algorithm-i

567. Max Area of Island

• https://leetcode.com/problems/max-area-of-island/?envType=study-plan&id=algorithm-i

문제 1

[733] Flood Fill

내 코드

from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:

        if image[sr][sc] ==color:
            return image

        startColor = image[sr][sc]
        n, m = len(image), len(image[0])

        queue = deque()
        queue.append((sr,sc))

        while queue:
            qx, qy = queue.popleft()
            image[qx][qy] = color

            for nx,ny in [(qx+1,qy), (qx-1,qy), (qx,qy+1), (qx,qy-1)]:
                if 0<=nx<n and 0<=ny<m and image[nx][ny]==startColor:
                    queue.append((nx,ny))
        return image

문제 풀이 방법

주어진 color와 starting pixel 과의 색이 달라야하고, 다를 경우
동,서,남,북 방향에서 starting pixcel 과의 요소가 같으면 주어진 color로 원소를 바꿔주는 문제로 dfs 혹은 bfs로 풀면 되는 문제이다.
여기서 queue를 활용해서 bfs로 풀었다.
재귀로 풀면 더 짧게 풀던데 난 아직 재귀 핸들링 어려워

증빙

---

문제 2

[695] Max Area of Island
https://leetcode.com/problems/max-area-of-island/description/?envType=study-plan&id=algorithm-i

내 코드

from collections import deque
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        dx, dy = [1,-1,0,0], [0,0,1,-1]
        def bfs(grid, i,j, row, col, visited):
            cnt = 1
            queue = deque()
            queue.append((i,j))
            visited[i][j] = 1
            while queue:
                qx, qy = queue.popleft()
                for q in range(4):
                    nx, ny = qx+dx[q], qy+dy[q]
                    if 0<=nx<row and 0<=ny<col and grid[nx][ny]==1 and not visited[nx][ny]:
                        queue.append((nx,ny))
                        visited[nx][ny]=1
                        cnt+=1
            return cnt
   
        row, col, answer = len(grid), len(grid[0]),0
        visited = [[0]*col for i in range(row)]
        for i in range(row):
            for j in range(col):
                if grid[i][j] ==1 and visited[i][j]==0:
                    answer = max(answer, bfs(grid, i, j, row, col, visited))

        return answer

문제 풀이 방법

bfs로 푸는 전형적인 문젠데..
별다른 조건이 없어서 쉽게 풀 수 있었음..
이제 이런 기본 문제는 안 헷갈리는 것 같기도 하고.. 아닌가..

증빙

여담

아문당 나와서 야외 코딩 하고 이제 tetd 먹으러 갈거임 굿