[1스4코2파] # 226 LeetCode 130. Surrounded Regions

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

Rule :

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

START :

[3코1파] 2023.01.04~ (226차)
[4코1파] 2023.01.13~ (218일차)
[1스4코1파] 2023.04.12~ (129일차)
[1스4코2파] 2023.05.03 ~ (107일차)

Today :

2023.08.18 [226일차]
graph
https://leetcode.com/problems/surrounded-regions/

130. Surrounded Regions

https://leetcode.com/problems/surrounded-regions/

문제 설명
![]

M x N의 board 행렬이 주어질 때, 'X'가 네 방향(위, 아래, 왼, 오)으로 둘러쌓여 있는 'O'는 'X'로 바꾸고, boundary에 있어서, 'X'가 네 방향으로 둘러 쌓이지 않은 'O'는 그대로 'O'로 둘 때,
메모리를 더 할당하지 않고 기존 board 자체에서 'O' 혹은 'X'로 유지 혹은 변환해서 return 함

문제 풀이 방법

(1) 처음에 O인 부분을 'X'로 다 바꿔줌
(2) mxn을 돌면서 경계선이 boundary인 부분을 기준으로 dfs를 이용해서 네 방향이 'O' 인 부분을 'T'로 변환
(3) 'T'를 'O'로 변환함

그리고 board 를 return 함

내 코드

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows, cols = len(board), len(board[0])

        def dfs(r,c):
            if r<0 or c<0 or r==rows or c==cols or board[r][c]!='O':
                return
            board[r][c] = 'T'
            dfs(r-1, c)
            dfs(r+1, c)
            dfs(r, c-1)
            dfs(r, c+1)

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O' and (r in [0,rows-1] or c in [0,cols-1]):
                    dfs(r,c)

        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':
                    board[r][c] = 'X'
        
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'T':
                    board[r][c] = 'O'   

증빙

여담

ㅃㄹㅃㄹ 끝내고 집에가자