UnionFind와 순서 강제로 탐색하기

문제 & 재정의

 

2583번: 영역 구하기

 위 문제는 상하좌우 방향에 인접한 블럭들의 크기를 구하는 전형적인 탐색 문제이다.

 

---

 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노드(윗쪽 노드)는 앞선 노드에서

확인을 했기 때문에 할 필요가 없는 것이다!