Table of contents
들어가며
걸린시간: 29분
처음에 문제를 읽으면서 연결된 영역을 찾는 전형적인 Flood Fill 알고리즘 문제인 것을 단번에 알 수 있었습니다. 🥸
그러나, 문제를 풀면서 넓이를 구하는 로직에서 조금 애를 먹었습니다.
접근
문제에서 2차원 배열에서 연결된 영역의 개수와 연결된 영역들 중에서 가장 큰 넓이를 가진 영역을 묻고 있습니다.
그래서 Flood Fill 알고리즘 문제임을 알게 됐어요.
Flood Fill 알고리즘의 경우, 시간 복잡도가 BFS Queue에 들어갔다 나온 원소의 개수만큼입니다.
그래서 이 문제에서는 이 최악의 상황에서의 시간 복잡도입니다.
n과 m이 각각 최대 500이기 때문에, 이 접근 방법은 시간 초과를 받지 않을 거라고 생각하고 문제를 풀기 시작했습니다.
구현
import sys
from collections import deque
input = sys.stdin.readline
class Solution:
def __init__(self):
pass
def outOfBound(self, cur_i, cur_j):
if cur_i < 0 or cur_i >= n:
return True
if cur_j < 0 or cur_j >= m:
return True
return False
def bfs(self, start_pos):
ret_area = 0
q = deque()
start_i, start_j = start_pos
dist[start_i][start_j] = 1
q.append(start_pos)
ret_area += 1
while q:
cur_i, cur_j = q.popleft()
# print(f"cur pos: {cur_i, cur_j}")
for di, dj in zip(deltaI, deltaJ):
next_i, next_j = cur_i + di, cur_j + dj
if self.outOfBound(next_i, next_j):
continue
if matrix[next_i][next_j] == 0:
continue
if dist[next_i][next_j] > 0:
continue
dist[next_i][next_j] = dist[cur_i][cur_j] + 1
q.append((next_i, next_j))
ret_area += 1
# print(f"{next_i, next_j} appended for next pos")
return ret_area
def floodFill(self):
num_pic = 0
max_area = 0
for start_i, start_j in startPosCandList:
if dist[start_i][start_j] > 0:
continue
num_pic += 1
max_area_cand = self.bfs((start_i, start_j))
if max_area_cand > max_area:
max_area = max_area_cand
for i in range(n):
for j in range(m):
if dist[i][j] > max_area:
max_area = dist[i][j]
# print(matrix)
# print(startPosCandList)
# for i in range(n):
# for j in range(m):
# print(dist[i][j], end=" ")
# print()
print(num_pic)
print(max_area)
if __name__ == "__main__":
n, m = map(int, input().strip().split())
matrix = [[*map(int, input().strip().split())] for _ in range(n)]
dist = [[0 for __ in range(m)] for _ in range(n)]
deltaI = (1, -1, 0, 0)
deltaJ = (0, 0, 1, -1)
startPosCandList = []
for i in range(n):
for j in range(m):
if matrix[i][j] == 1:
startPosCandList.append((i, j))
sol = Solution()
sol.floodFill()일단 처음에 주어진 2차원 배열 matrix를 한번 훑으면서 원소의 값이 1인 원소의 좌표 (i, j)를 얻어내서, startPosCandList(BFS 시작 위치 후보 리스트)라는 리스트에 저장을 해놨습니다.
- 그리고 BFS 시작 위치 후보 리스트에서 좌표를 한개씩 빼서, 해당 위치에서 BFS를 시작했습니다. (이미 BFS를 통해서 방문이 완료됐다면, 해당 시작 위치는 건너 뜁니다.)
- 그리고 BFS가 다 끝나면, 큐에 들어갔다 나온 개수 만큼을 BFS 함수에서 리턴을 했습니다. (큐에 들어 갔다 나온 원소 개수가 곧 이어진 영역의 넓이이기 때문이죠.)
1)을 반복한 횟수가 곧 이어진 영역의 개수이고, 2)에서 구한 이어진 영역의 넓이들 중 최대값이 그림의 최대 영역 넓이였습니다.😮👍
감사합니다 꾸-벅