정글 8일차

일주일이 지났다.
학습속도가 점점 느려진다.
지금까지 단 한 문제를 풀었다.
중요한 배움이 있었지만 쓴 시간이 너무 많다.

오늘 배운 것

1. 완전탐색

1-1. 안전 영역(백준 2468)

간단할 것으로 예상해 호기롭게 도전.
예상대로 구현은 금방 되었으나 예외를 찾지 못해 7시간을 헤맸다.
앞으로는 악으로 붙잡고 늘어지는 습관은 삼가야겠다...
핵심은 섬의 개수를 구하는 방식이다.
재귀를 안 쓰고 풀려 하니 많이 복잡해졌는데
왼쪽에서 오른쪽으로, 위에서 아래로 섬에 번호를 매긴다.
그러다 마지막 줄처럼 다른 섬끼리 만나는 경우가 생기는데
별도의 배열에 어떤 섬들을 병합하였는지 기록해둔다.
그리고 마지막에 섬들을 병합하고 개수를 세는데 여기서 문제가 발생했다.

import sys

N = int(sys.stdin.readline())
A = [[int(i) for i in sys.stdin.readline().split()] for _ in range(N)]

def main() -> None:
    # 수위(level)을 입력받아 수위 이하인 경우 0으로 표시해 리턴
    def _flood(level :int) -> list:
        is_dry = [[e if e > level else 0 for e in row] for row in A]
        return is_dry
    
    def _check_neighbor(is_dry :list, neighbor_list :list, merged_islands_list :list, row_idx :int, col_idx :int) -> int:
        r_neighbor = c_neighbor = -1
        if row_idx > 0 and is_dry[row_idx-1][col_idx]>=1:
            r_neighbor = neighbor_list[row_idx-1][col_idx]
        if col_idx > 0 and is_dry[row_idx][col_idx-1]>=1:
            c_neighbor = neighbor_list[row_idx][col_idx-1]
        if r_neighbor == -1:
            return c_neighbor
        elif c_neighbor == -1:
            return r_neighbor
        elif r_neighbor == c_neighbor:
            return r_neighbor
        else:
            merge_island = (min(r_neighbor, c_neighbor), max(r_neighbor, c_neighbor))
            if merge_island not in merged_islands_list:
                merged_islands_list.append(merge_island)
            return merge_island[0]
        
    def _make_island(is_dry: list) -> int:
        def find_root(island_map, island):
            while island_map[island] != island:
                island_map[island] = island_map[island_map[island]]  # 경로 압축
                island = island_map[island]
            return island
        
        def union_islands(island_map, island1, island2):
            root1 = find_root(island_map, island1)
            root2 = find_root(island_map, island2)
            if root1 != root2:
                island_map[root2] = root1  # 병합

        merged_islands_list = []
        new_island = 1
        N = len(is_dry)
        M = len(is_dry[0])
        neighbor_list = [[] for _ in range(N)]
        island_map = {}  # 각 섬 번호의 루트를 기록

        for i in range(N):
            for j in range(M):
                if is_dry[i][j] == 0:
                    neighbor_list[i].append(-1)
                    continue
                island_num = _check_neighbor(is_dry, neighbor_list, merged_islands_list, i, j)
                if island_num == -1:
                    neighbor_list[i].append(new_island)
                    island_map[new_island] = new_island
                    new_island += 1
                else:
                    neighbor_list[i].append(island_num)
                    if island_num not in island_map:
                        island_map[island_num] = island_num

        # 병합 처리
        for island1, island2 in merged_islands_list:
            union_islands(island_map, island1, island2)

        # 고유 섬의 루트 번호 개수 세기
        unique_islands = set(find_root(island_map, island) for island in island_map.keys())


        return len(unique_islands)
        
    unique_heights = []
    for row in A:
        for e in row:
            if e not in unique_heights:
                unique_heights.append(e)
    
    max_island = 1
    unique_heights.sort()
    unique_heights.pop(-1)
    for i in unique_heights:
        is_dry = _flood(i)
        islands = _make_island(is_dry)
        max_island = max(max_island, islands)
    print(max_island)

main()

이 코드는 정상적으로 동작한다.
하지만 나는 병합한 횟수==병합으로 사라진 개수라고 생각해 빼주면 될 것이라고 생각했는데 자꾸 오답이 나왔다.

0 0 0 0 0
1 0 0 0 0
0 2 0 0 3
4 2 0 5 3
4 2 2 2 2
# 병합: [(2,4), (2,5), (3,5), (2,3)]
# 병합횟수: 4
# 섬 최고 인덱스: 5
# 섬 개수: 2
# 최고 인덱스-병합횟수: 1(오답)

(2, 3, 4, 5)처럼 여러 섬들이 병합되는 경우 순환되는 구조로 병합이 발생한다.
이 경우를 고려하지 못 했다.
GPT의 도움을 받아 위와 같이 고친 것이다.
특히 이 부분이 중요한데

def find_root(island_map, island):
    while island_map[island] != island:
        island_map[island] = island_map[island_map[island]]  # 경로 압축
        island = island_map[island]
    return island

def union_islands(island_map, island1, island2):
    root1 = find_root(island_map, island1)
    root2 = find_root(island_map, island2)
    if root1 != root2:
        island_map[root2] = root1  # 병합

# 경로 압축
부분에 island_map[island]:병합하는 root섬을 저장하여 나중에 root섬만 수정하면 전체 섬에 반영되도록 했다.
딕셔너리가 mutable자료형임을 이용한 것.

위 케이스를 계속 예로 들면

# 병합대상: [(2,4), (2,5), (3,5), (2,3)]
island_map = {1: 1, 
			  2: 2, 
              3: island_map[2], 
              4: island_map[2], 
              5: island_map[3]}

같은 방식으로 저장되어 나중에 2번 섬이 병합되더라도 다른 섬들까지 반영되도록 한 것이다.

처음에는 왜 저런 방식으로 하는지 이해가 안 됐다.
랜덤한 섬 지도를 입력하는 방식으로 내 코드와 결과를 비교해보니 반례들을 찾을 수 있었다.

for _ in range(1000):
    is_dry = [[round(random.random()) for _ in range(N)] for _ in range(N)]
    _make_island(is_dry)

사실 그냥 DFS로 탐색시키면 쉽게 풀린다.