[LeetCode] 130. Surrounded Regions (Python) 풀이

2023. 12. 9. 13:53·Algorithm (PS)/LeetCode
728x90

문제 요구사항 

  • "O" 를 "X"로 flip 하라. 
  • 단, 가장 자리에 맞닿은 "O"의 경우 뒤집으면 안되며, 이 가장자리와 인접한 다른 "O"의 경우에도 뒤집지 않는다. 

풀이 방법 (알고리즘 : BFS)

  • 우선 M*N 배열에서 "O" 가 있는 칸의 위치 (i, j) 를 구한다. -> island 집합에 저장
  • 가장자리에 있는 "O" 를 찾아서, "O"와 인접한 칸들까지 BFS로 찾아서 island 라는 집합에서 빼준다. 
  • 남아있는 좌표들은 X 로 flip 이 가능한 위치이므로 모두 변환해 준다. 
from collections import deque

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        N = len(board[0])
        M = len(board)

        island = set()  # O 를 섬으로 취급

        # 내부에 있는 O 확인하기
        for i in range(M):
            for j in range(N):
                if board[i][j] == "O":
                    island.add((i, j))

        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        # BFS

        def bfs(x, y):
            queue = deque([])
            queue.append((x, y))
            visited[x][y] = True
            while queue:
                x, y = queue.popleft()
                island.discard((x, y))  # 가장자리는 X 처리에서 제외 필요함
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < M and 0 <= ny < N and board[nx][ny] == "O" and not visited[nx][ny]:
                        queue.append((nx, ny))
                        visited[nx][ny] = True

        visited = [[False] * N for _ in range(M)]
        for i in range(M):
            for j in range(N):
                if (i == M - 1 or i == 0 or j == N - 1 or j == 0):
                    if not visited[i][j] and board[i][j] == "O":
                        print(i, j)
                        bfs(i, j)

        # O -> X flip
        for x, y in island:
            board[x][y] = "X"
728x90

'Algorithm (PS) > LeetCode' 카테고리의 다른 글

[LeetCode] Median of Two Sorted Arrays - Python 풀이  (0) 2024.07.30
[LeetCode] Sort-List (Python 풀이)  (0) 2024.07.16
[Leetcode] 894. All Possible Binary Trees (Python)  (0) 2024.07.01
[LeetCode] 54. Spiral Matrix - Python  (0) 2024.01.06
[LeetCode] 79. Word Search - Python 풀이  (0) 2023.12.18
'Algorithm (PS)/LeetCode' 카테고리의 다른 글
  • [LeetCode] Sort-List (Python 풀이)
  • [Leetcode] 894. All Possible Binary Trees (Python)
  • [LeetCode] 54. Spiral Matrix - Python
  • [LeetCode] 79. Word Search - Python 풀이
minjiwoo
minjiwoo
Data Engineering과 Cloud Native 기술에 대해 Dive Deep 하는 플랫폼 엔지니어가 되는 것을 목표로 하고 있습니다. 경험과 공부한 내용을 기록하며 지속가능한 엔지니어가 되는 것이 꿈입니다.
minjiwoo
minji's engineering note
minjiwoo
전체
오늘
어제
  • 분류 전체보기 (613)
    • Data Engineering (42)
      • Apache Spark (11)
      • Databricks & Delta Lake (9)
      • Airflow (3)
      • SQL (6)
      • Trouble Shooting (2)
      • Hadoop (2)
      • MLOps (1)
    • Cloud Engineering (104)
      • AWS (23)
      • Linux 🐧 (29)
      • Docker 🐳 (21)
      • Kubernetes ⚙️ (20)
      • Ansible (10)
    • Computer Science (87)
      • 네트워크 (9)
      • 운영체제 (25)
      • 정보처리기사 (48)
      • CS 기술 면접 스터디 (3)
    • Programming Languages (27)
      • Python (17)
      • C와 C++ (10)
    • Backend (5)
      • Django (2)
    • 프로젝트 (2)
      • 테크포임팩트 (2)
    • iOS (11)
      • 레이블러리 (2)
    • Algorithm (PS) (275)
      • LeetCode (6)
    • 개발일기 (30)
      • 내돈내산 후기🎮 (3)
      • 개발자 취준생 (5)
      • Today I Learned (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • Hi there

인기 글

태그

  • 코딩테스트
  • ansible
  • 백준
  • BFS
  • Databricks
  • 빅데이터
  • 쿠버네티스
  • linux
  • 스파크
  • 알고리즘
  • Swift
  • 데이터엔지니어
  • SPARK
  • EC2
  • dfs
  • 리눅스
  • Leetcode
  • 데이터엔지니어링
  • 프로그래머스
  • 데이터브릭스
  • 운영체제
  • docker
  • 클라우드
  • dp
  • python
  • 파이썬
  • 카카오코딩테스트
  • Kubernetes
  • AWS
  • 백트래킹

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
minjiwoo
[LeetCode] 130. Surrounded Regions (Python) 풀이
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.