문제 & 재정의
위 문제는 상하좌우 방향에 인접한 블럭들의 크기를 구하는 전형적인 탐색 문제이다.
UnionFind로 탐색하기
탐색이 가능한 것은 (x, y)를 기준으로 (x+-1, y)와 (x, y+-1) 총 4개의 경우로 탐색이 가능하다.
이 상하좌우 인접을 하나하나 탐색하는게 아니라, 각각의 그룹으로 묶을 수 있다면?
그룹별 크기를 구하는건 자연스럽게 할 수 있다.
그룹으로 묶는 방법은 여러가지가 있지만 MST를 구현할 때 사용하는 UnionFind 알고리즘을 사용할 수 있다.
union_find = UnionFind(h*w)
for y in range(h):
for x in range(w):
if field[y][x]:
continue
node = y*w + x
r_node = node + 1
d_node = node + w
l_node = node - 1
u_node = node - w
if (0 <= x+1 < w) and not field[y][x+1]:
union_find.union(node, r_node)
if (0 <= y+1 < h) and not field[y+1][x]:
union_find.union(node, d_node)
if (0 <= x-1 < w) and not field[y][x-1]:
union_find.union(node, l_node)
if (0 <= y-1 < h) and not field[y-1][x]:
union_find.union(node, u_node)
순서 강제하기
위의 코드에서 몇 줄의 코드를 지워도 똑같이 동작한다.
union_find = UnionFind(h*w)
for y in range(h):
for x in range(w):
if field[y][x]:
continue
node = y*w + x
r_node = node + 1
d_node = node + w
if (0 <= x+1 < w) and not field[y][x+1]:
union_find.union(node, r_node)
if (0 <= y+1 < h) and not field[y+1][x]:
union_find.union(node, d_node)
이유는 탐색을 좌측상단부터, 우측하단 방향으로 탐색을 하기 때문이다.
시작 지점에는 좌상단이 없기 때문에 할 필요가 없다.
그리고 좌상단에서 우하단 방향으로 탐색을 하기 때문에
특정 시점의 노드에서, L노드(왼쪽 노드)와 U노드(윗쪽 노드)는 앞선 노드에서
확인을 했기 때문에 할 필요가 없는 것이다!
'알고리즘' 카테고리의 다른 글
최단 경로 관리하기 (0) | 2024.01.27 |
---|---|
DP를 정의 하는 방법 (0) | 2024.01.25 |
PrefixSum 갱신 빠르게 하기 (0) | 2024.01.23 |
날짜 비교하기 (0) | 2024.01.22 |
Greedy에서 상위/하위 호환 처리하기 (1) | 2024.01.22 |