Leetcode Python - 130. Surrounded Regions
Leetcode #130 - Surrounded Regions
리트코드의 문제 130 ‘Surrounded Regions’을 파이썬으로 풀어 보도록 하겠습니다. 주어진 m*n matrix board에 있는 ‘X’,’O’를 경계에서 이어져있는 ‘O’만 남기고 나머지를 ‘X’로 바꾸는 문제입니다.
예를 들면 아래와 같습니다.
# input
board = [
["X","X","X","X"],
["X","O","O","X"],
["X","X","O","X"],
["X","O","X","X"]
]
# output
board = [
["X","X","X","X"],
["X","X","X","X"],
["X","X","X","X"],
["X","O","X","X"]
]
discuss를 보며 풀어 보도록 하겠습니다.
포인트는 boundary 경계쪽에서 시작되는 dfs를 구현하는 것입니다. 그렇기 때문에 ‘O’가 위에서 시작되는지 아니면 아래에서 시작되는지, 혹은 왼쪽에서 시작되는지 아니면 오른쪽에서 시작되는지 체크해야합니다.
위 혹은 아래에서 시작되는 dfs
for i in [0, len(board)-1]:
for j in range(len(board[0])):
self.dfs(board, i, j)
왼쪽 혹은 오른쪽에서 시작되는 dfs
for i in range(len(board)):
for j in [0, len(board[0])-1]:
self.dfs(board, i, j)
’.’이면 ‘O’로 나머지는 ‘X’로,
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '.':
board[i][j] = 'O'
dfs 구현, 어느 쪽에서든 이전 것이 ‘O’이 아니면 진행되지 않음
def dfs(self, board, i, j):
if 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] == 'O':
board[i][j] = '.'
self.dfs(board, i+1, j)
self.dfs(board, i-1, j)
self.dfs(board, i, j+1)
self.dfs(board, i, j-1)
전체 코드는 아래와 같습니다.
def solve(self, board):
if not board or not board[0]:
return
for i in [0, len(board)-1]:
for j in range(len(board[0])):
self.dfs(board, i, j)
for i in range(len(board)):
for j in [0, len(board[0])-1]:
self.dfs(board, i, j)
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '.':
board[i][j] = 'O'
def dfs(self, board, i, j):
if 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] == 'O':
board[i][j] = '.'
self.dfs(board, i+1, j)
self.dfs(board, i-1, j)
self.dfs(board, i, j+1)
self.dfs(board, i, j-1)
시간복잡도는 O(n) : 모든 element를 방문 *2 = 2n
공간복잡도는 O(1) : 상수 안에서 가능