[코테] Leetcode 130. Surrounded Region

1. 문제

m x n 크기의 매트릭스 board가 주어짐. 이 매트릭스는 X와 O로 구성되어 있으며, 이 중에서 O로 이루어진 영역 중에서 로 둘러싸인 영역을 찾아 그 영역의 O를 모두 X로 바꾸기

연결(Connect): 셀은 인접한 셀과 가로/세로로 연결될 수 있음
영역(Region): 모든 O 셀을 연결해 영역을 형성
둘러싸임(Surround): 영역이 보드의 가장자리와 연결되지 않고, 완전히 X 셀로 둘러싸여 있는 경우 둘러싸인 것으로 간주
영역의 캡처: 둘러싸인 영역의 모든 O를 X로 변환

2. 예시

(1)

Input: board = [["X","X","X","X"],
                ["X","O","O","X"],
                ["X","X","O","X"],
                ["X","O","X","X"]]

Output: [["X","X","X","X"],
         ["X","X","X","X"],
         ["X","X","X","X"],
         ["X","O","X","X"]]

(2)

Input: board = [["X"]]

Output: [["X"]]

3. 코드창

4. 풀이 아이디어

'덩어리'라는 semantic을 코드에 어떻게 구현하는가
→ 애초에 BFS의 시작(current_node)을 그 덩어리 중 한 부분으로 잡기
→ 그 다음 방문할 인접노드의 기준으로 그 덩어리의 특성(가령 뭐 X라던지 O이라던지) 조건을 사용. 그럼 같은 덩어리에 속하는 애들만 방문하게 됨.

⭐️BFS의 시작노드는 어디
처음에는 테두리와 접하지 않은 'Surrounded'된 O들을 추출하려고 했다.
근데 반대로, 테두리와 접하는 애들을 O덩어리를 추출하는 게 낫겠다 싶었다. 시작노드를 '테두리에 있는 O노드'로 픽스하면 된다

테두리에서 시작해 연결된 'O'를 찾고, 이를 제외한 나머지 'O'를 'X'로 변환하하자!

5. Seudo Code

1. (0,0)~(m,0), (m,0)~(m,n), (m,n)~(0,n), (0,n)~(0,0)의 테두리를 탐색
2. X인 애들은 패스, O인 애들만 방문하여 다음을 시행
3. O노드 방문 -일단 방문 기록 업데이트 - 상하좌우에 있는 애들을 방문예정 노드에 등록
4. 또 방문 - 방문기록 등록 - 상하좌우를 방문 예정 노드에 등록 .. 반복

6. 처음 작성한 Code

함수 정의

from collections import deque

dx = [-1, 1, 0, 0]  # 상하좌우 이동 
dy = [0, 0, 1, -1]

# 테두리 인덱스를 리스트로 반환하는 함수
def find_outer(board): 
    global m, n 
    m, n = len(board), len(board[0])  # 보드 크기 
    board_outer_index = []  # 테두리 리스트
    for a in range(m):
        for b in range(n):
            if (a == 0 or a == (m - 1)) or (b == 0 or b == (n - 1)):  # 테두리 리스트에 추가
                board_outer_index.append([a, b])  
    return board_outer_index  # 테두리 리스트 반환 

# bfs 수행하는 함수 
def bfs(board, current_node, visited):
    queue = deque()  # 대기열 초기화 
    queue.append(current_node)  # 현재노드를 대기열에 추가
    visited.append(current_node)  # 현재노드 방문 기록
    
    while queue: # 대기열이 빌 때까지
        r, c = queue.popleft()  # 대기열에서 하나 꺼내서 인덱스 저장
        for i in range(4): # 상하자우
            new_r = r + dx[i]  # 인접노드의 행
            new_c = c + dy[i]  # 인접노드의 열
            if new_r < 0 or new_r >= m or new_c < 0 or new_c >= n:  # 보드 범위 벗어나면 무시(=방문X)
                continue
            if board[new_r][new_c] == "X":  # X면 무시
                continue
            if [new_r, new_c] in visited:  # 이미 방문했으면 무시
                continue
            if board[new_r][new_c] == "O":  # O이면 방문               visited.append([new_r, new_c])  # 방문기록에 추가
                queue.append([new_r, new_c])  # 대기열에 추가
    
    return visited  # 방문기록(인덱스) 출력

수행

# 입력
board = [["X", "X", "X", "X"],  
         ["X", "O", "O", "X"],
         ["X", "O", "O", "X"],
         ["X", "O", "X", "X"]]
         
# 테두리 인덱스 구하기 
board_outer_index = find_outer(board) 

# BFS 수행
for index in board_outer_index: # 테두리에 있느 ㄴ
    visited = []  # 방문 리스트 초기화
    if board[index[0]][index[1]] == "X":  # 외곽 셀이 'X'인 경우 무시
        continue
    if board[index[0]][index[1]] == "O":  # 외곽 셀이 'O'인 경우
        print(bfs(board, index, visited)) 

7. 수정한 Code

클래스

from collections import deque  
from typing import List 

class Solution:   
        def find_outer(board):  
            m, n = len(board), len(board[0])  
            return [[a, b] for a in range(m) for b in range(n) if a == 0 or a == m-1 or b == 0 or b == n-1]  

        def bfs(board, start, visited):  
            queue = deque([start])  
            visited.add(tuple(start))  
            while queue:  
                r, c = queue.popleft()  
                for i in range(4):  
                    new_r, new_c = r + dx[i], c + dy[i] 
                    if 0 <= new_r < len(board) and 0 <= new_c < len(board[0]) and board[new_r][new_c] == "O":  
                        # 새 위치가 범위 내에 있고 O
                        if (new_r, new_c) not in visited:  # 아직 방문 안했으면 방문기록추가, 대기열에 추가 
                            visited.add((new_r, new_c))  
                            queue.append([new_r, new_c]) 
        
        dx = [-1, 1, 0, 0]  
        dy = [0, 0, 1, -1]
        visited = set()  # 방문노드 기록용
        board_outer_index = find_outer(board)          
        for index in board_outer_index:  # 테두리 순회
            if board[index[0]][index[1]] == "O":  # O라면
                bfs(board, index, visited)  # BFS 수행

        # 행,열 순회하며 보드 수정하고 반환
        for i in range(len(board)):  
            for j in range(len(board[0])):  
                if (i, j) in visited: # 아까 저장한 건 O그대로
                    board[i][j] = "O"  
                else:  # 나머지는 싹 다 X 
                    board[i][j] = "X" 

8. 정답 코드

- 테두리에 붙어있는 O덩어리만 냅두고 나머지 O를 전부 다 X로 바꾸는 클래스와 함수를 작성
- board라는 인풋값이 정확히 들어았는지 확인
- if not board: 는 board가 비어있을 경우 False를 반환
- dfs 구현
- dfs: 입력값으로 현재 노드의 행인덱스와 열인덱스 받음
- dfs자체가 애초에 정의할 때부터 재귀함수인가? OR 이 함수를 활용할 때 재귀적으로 사용하나? -> 전자. 
- dfs 함수는 그 행,열 인덱스에 해당하는 노드가 행렬 범위 내에 있고, 값이 O이면 그 값을 "B" 같은 다른 문자로 치환(나중에 B인 애들을 제외한 모든 애들을 'X'로 변환할거니까)
- 테두리에 있는 O를 dfs의 시작노드로 설정하고, 거기서 계속 dfs 수행
- 테두리 애들의 인덱스 뽑기: 하나의 리스트를 뽑고 거기서 for문을 돌려도 되지만, 그냥 가로세로 각 리스트에 대해서 각각 for문 작성이 편하다
- B인 애들 빼고 다 X 로 변환  

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return
        
        m, n = len(board), len(board[0])
        
        # DFS to mark all the regions connected to the border as 'B'
        def dfs(i, j):
            if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
                board[i][j] = 'B'
                dfs(i+1, j)
                dfs(i-1, j)
                dfs(i, j+1)
                dfs(i, j-1)
                
        for i in range(m):
            dfs(i, 0)
            dfs(i, n-1)
            
        for j in range(1, n-1):
            dfs(0, j)
            dfs(m-1, j)
            
        # Flip all 'O' in the surrounded regions to 'X', and restore 'B' to 'O'
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'B':
                    board[i][j] = 'O'

기타 정리 내용

BFS

• 큐 자료구조, deque 라이브러리 사용

Pseudo Code

• 라이브러리 불러오고
• bfs 함수 정의하기

1. 방문기록 기록할 거 준비(visited)
2. 방문예정에 출발지만 두기(queue)
3. 방문예정이 빌 때까지,(while queue)
   3-1. 이제 내가 왔으니 방문예정에서 빼 그리고 방문표시 남겨(pop, append)
   3-2. 여기랑 연결된 애들 방문예정에 넣어(append)

• 큐 = 방문예정 리스트
• 도착 - 거길 방문예정에서 제거 & 방문기록에 추가 - 방문예정 업데이트

디버깅 과정에서 발견한 실수

이중 for문

아래처럼 쓴 걸 뒤늦게 발견..😅

for a,b in range(m) and range(n):

a는 0부터 m-1까지, b는 0부터 n-1까지해서 구구단처럼 총 mxn가지 경우의 수에 대해 순회하고자 한다면 아래처럼 해야지
cf.zip은 a 값 하나에 대해 b 값도 반드시 하나가 대응되어 짝지어 순회

for a in range(m):
	for b in range(n):

BFS면 그냥 일단 쓰고 시작

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [[0] * n for _ in range(m)]

---

for dx, dy in directions:
	nx, ny = cx + dx, cy + dy