•
•
문제 설명 : land와 water를 각각 1, 0으로 나타낸 2차원 배열이 있다. 섬의 갯수를 구해서 반환한다.
•
풀이 방법
◦
처음에는 하나의 land와 연결된 land를 구해야하는 방식이기 때문에, BFS로 접근하였다.
▪
하지만, 시간 복잡도가 발생하였다.
◦
DFS로 풀어보니, 오히려 DFS가 더 빠른 결과를 보여주며 Solved가 가능하였다.
◦
기존에는 DFS는 재귀로 처리하기 때문에 BFS가 평균적으로 더 빠르다고 생각했는데, 그렇지 않았다.
▪
궁금해서, 두 방식에 대해 비교를 해보았다. (아래 내용 참고)
•
시간복잡도 :
•
성공 코드 (DFS)
visit이라는 별도의 방식을 써도 되지만, 그냥 기존 grid 값을 0으로 변경하여 visit으로 처리하였다.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
def dfs(x, y):
grid[x][y] = 0
if 0 <= x + 1 < len(grid) and grid[x + 1][y] == '1':
dfs(x + 1, y)
if 0 <= x - 1 < len(grid) and grid[x - 1][y] == '1':
dfs(x - 1, y)
if 0 <= y + 1 < len(grid[0]) and grid[x][y + 1] == '1':
dfs(x, y + 1)
if 0 <= y - 1 < len(grid[0]) and grid[x][y - 1] == '1':
dfs(x, y - 1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
Python
복사
•
실패 코드(BFS)
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
queue = deque()
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
queue.append((i, j))
while queue:
x, y = queue.popleft()
grid[x][y] = '0'
if 0 <= x + 1 < len(grid) and grid[x + 1][y] == '1':
queue.append((x + 1, y))
if 0 <= x - 1 < len(grid) and grid[x - 1][y] == '1':
queue.append((x - 1, y))
if 0 <= y + 1 < len(grid[0]) and grid[x][y + 1] == '1':
queue.append((x, y + 1))
if 0 <= y - 1 < len(grid[0]) and grid[x][y - 1] == '1':
queue.append((x, y - 1))
count += 1
return count
Python
복사
두 방식의 비교
BFS가 더 오래 걸렸다는 것은, Queue에서 탐색하는 좌표가 불필요하게 많이 들어갔음을 의미한다.
하나의 좌표를 처리할 때, 4번의 비교 작업을 거치기 때문에 최대한 탐색 자체를 줄여야한다.
시간 복잡도 발생 Case (20 X 15 이차원 배열)
위 케이스에 대해, DFS 방식의 함수 동작 횟수와 BFS 방식의 Queue Pop 횟수를 비교해보았다.
•
BFS 방식 : 38832922번 POP 진행
•
DFS 방식 : 269번 dfs 함수 호출
엄청난 차이다… 
이렇게까지 차이나는 이유는 뭘까?
이렇게까지 차이나는 이유는 뭘까?아까 언급했듯, 가장 중요한 건 불필요한 탐색 자체를 줄이는 것이다.
위 DFS 방식과 BFS 방식의 가장 큰 차이점은, 바로 방문한 좌표 여부를 실시간으로 처리했느냐이다.
DFS의 경우, island 좌표를 발견하면 현 좌표의 다른 방향은 나중에 확인하고 해당 좌표로 먼저 추가 확인하는 재귀 구조이다.
이 과정에서, dfs의 함수 첫 부분에는 grid 배열의 방문 여부를 현 좌표를 water로 변경하여 처리한다.
BFS의 경우, Queue에 방문 가능한 좌표를 모두 append(이러한 좌표를 A라고 하자)한다.
하지만, 해당 좌표들은 바로 방문 처리되지 않고 pop처리 되야만 방문이 처리된다.
그렇다면 추가된 좌표(B라고 하자)들이 pop되기 전 앞 좌표들이 해당 좌표(A)를 추가 확인한다면, 방문처리 되기 전이기 때문에 불필요하게 큐에 append된다.
하나의 좌표에서만 이러한 동작이 4번씩 일어날 수 있기 때문에, 큐에 쌓이는 좌표들이 기하급수적으로 늘어난다.
이는 방문 여부를 실시간으로 처리하여, 개선이 가능하다.
단순히 append만 하지 않고, 탐색한 좌표에 대한 처리를 바로 진행하는 것이다.
추가 좌표 실시간 방문 처리 추가 확인
현재 좌표 추가 확인
BFS 코드로도 통과가 가능함을 확인하였다 :)
DFS / BFS와 같이 특정한 방식을 중요한 것이 아닌, 방문 지점을 실시간으로 처리하여 불필요한 탐색을 얼마나 줄이는지가 중요한 것 같다.
다만, BFS는 공간 복잡도가 DFS보단 더 크기 때문에 이 부분은 고려가 필요하다.
