물로만 이루어진 무한한 2차원 격자(grid)가 있다고 가정해 보겠습니다. 우리는 이 격자 위에 땅 블록을 하나씩 추가할 수 있습니다. 각 좌표가 [r, c] 형태(r은 행, c는 열)로 담긴 리스트 land_requests가 주어졌을 때, 땅 블록을 하나씩 추가할 때마다 현재 존재하는 섬(island)의 개수를 순서대로 기록한 리스트를 구하는 것이 목표입니다.
예를 들어 입력이 다음과 같다면,
land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]
출력은 [1, 2, 2, 2, 1]이 됩니다.
[1, 1]에 땅을 추가하면 섬 1개
[2, 4]에 땅을 추가하면 서로 떨어져 있으므로 섬 2개
[1, 2]를 추가하면 [1, 1]과 인접하지만 [2, 4]와는 연결되지 않아 여전히 섬 2개
[1, 4]를 추가하면 [2, 4]와 인접하므로 합쳐져 섬 2개
[1, 3]을 추가하면 모든 땅이 하나로 연결되어 섬 1개
접근 방법: 유니온-파인드(Union-Find)
이 문제는 매번 새 블록마다 전체 격자를 탐색하면 비효율적입니다. 대신 유니온-파인드(서로소 집합) 자료구조를 사용하면 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
새 땅 블록이 추가되면 일단 새로운 섬(집합) 하나가 생긴 것으로 간주하고 섬 개수를 1 증가시킵니다.
상하좌우 네 방향을 확인하여 이미 존재하는 땅과 인접해 있다면 두 집합을 합칩니다(union). 집합이 하나씩 합쳐질 때마다 섬 개수는 1 감소합니다.
각 요청 처리 후의 섬 개수를 정답 리스트에 기록합니다.
알고리즘 단계
d: 상하좌우 방향을 나타내는 리스트 [(-1, 0), (0, 1), (1, 0), (0, -1)]idx: 각 땅 블록에 부여할 고유 번호mp: 좌표 → 블록 번호를 저장하는 맵p: 유니온-파인드의 부모(parent) 배열size: 각 집합의 크기를 저장하는 배열 (union 시 큰 집합에 작은 집합을 붙여 트리 균형 유지)comp: 현재 섬(연결 요소)의 개수ans: 각 단계별 섬 개수를 저장할 정답 리스트
search(u) 함수 — 루트 찾기
u가 자기 자신의 부모라면u가 루트이므로 그대로 반환합니다.그렇지 않으면 재귀적으로 루트를 찾고, 경로 압축(path compression)을 위해
p[u]를 루트로 갱신한 뒤 반환합니다.
connect(u, v) 함수 — 두 집합 합치기
pu = search(u),pv = search(v)로 각각의 루트를 찾습니다.두 루트가 같다면 이미 같은 섬이므로 아무것도 하지 않고 종료합니다.
루트가 다르면 두 섬이 합쳐지는 것이므로
comp를 1 감소시킵니다.크기 기반 합치기(union by size): 크기가 더 큰 집합의 루트를 부모로 삼고, 크기를 누적합니다.
메인 로직
land_requests의 각 요청(i, j)에 대해:좌표
(i, j)에 고유 번호idx를 할당하고mp에 저장p에는 자기 자신을 부모로 추가하고,size에는 1을 추가idx와comp를 각각 1 증가 (새 섬 생성)네 방향
d를 순회하며 인접 좌표(ni, nj)가mp에 존재하면connect()호출로 집합을 병합현재
comp값을ans에 추가
모든 요청을 처리한 후
ans를 반환합니다.
구현 예제
d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
class Solution:
def search(self, u):
if u == self.p[u]:
return u
self.p[u] = self.search(self.p[u]) # 경로 압축
return self.p[u]
def connect(self, u, v):
pu = self.search(u)
pv = self.search(v)
if pu == pv:
return # 이미 같은 섬
self.comp -= 1 # 두 섬이 하나로 합쳐짐
if self.size[pu] >= self.size[pv]:
self.p[pv] = pu
self.size[pu] += self.size[pv]
else:
self.p[pu] = pv
self.size[pv] += self.size[pu]
def solve(self, land_requests):
self.idx = 0
self.mp = dict()
self.p = []
self.size = []
self.comp = 0
ans = []
for request in land_requests:
i, j = request
self.mp[(i, j)] = self.idx # 좌표에 고유 번호 부여
self.p.append(self.idx)
self.size.append(1)
self.idx += 1
self.comp += 1 # 일단 새 섬으로 카운트
for k in d: # 네 방향의 인접 땅 확인
ni = i + k[1]
nj = j + k[0]
if (ni, nj) in self.mp:
self.connect(self.mp[(i, j)], self.mp[(ni, nj)])
ans.append(self.comp)
return ans
ob = Solution()
land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]
print(ob.solve(land_requests))입력
[[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]]
출력
[1, 2, 2, 2, 1]
복잡도 분석
시간 복잡도: 경로 압축과 크기 기반 합치기를 함께 사용하면 각 연산의 평균 시간은 거의 상수(O(α(N)), α는 아커만 함수의 역함수)이므로, 전체 시간 복잡도는 O(K·α(K))입니다. 여기서 K는 요청의 개수입니다.
공간 복잡도: 좌표 맵과 부모/크기 배열에 O(K)의 공간이 필요합니다.