1568. Minimum Number of Days to Disconnect Island

[zeikar]

Problem link

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/

Problem Summary

2d 배열로 맵이 주어진다. 0은 바다, 1은 육지.
1을 0으로 바꿔서 섬이 2개로 나눌 수 있는 최소 횟수를 구하는 문제.

Solution

엄청 어려워 보이는데 간단하게 풀 수 있는 방법이 있다.
답은 무조건 0, 1, 2 중 하나이다.

일단 0, 1은 그럴 수 있는데 왜 2번만에 모든 섬을 2개로 나눌 수 있을까? 섬이 어떻게 생겼든 꼭지점을 나눠서 섬을 2개로 만들 수 있기 때문이다.

에디토리얼 참고.

그렇게 되면 문제가 간단해지고 1번만에 섬을 2개로 나눌 수 없으면 2를 출력하면 정답이 된다.

Tarjan's Algorithm

단순 DFS로 섬 개수를 판단하면 O((mn)^2)가 되는데 O(mn)으로 풀 수 있는 알고리즘이 존재한다. 바로 Tarjan 알고리즘이다.

복잡해서 간단히 소개만 해보자면 그래프에서 강력 연결 요소(SCC) 를 찾는 알고리즘이다. SCC는 그래프 내에서 모든 노드가 서로 도달 가능한 부분 그래프이고 여기서는 섬이 분리되는 단절점(Articulation Point)을 찾는 것이다.

더 자세한 코드는 에디토리얼 참고.

Source Code

class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        def dfs(x, y, visited):
            if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or grid[x][y] == 0:
                return
            visited[x][y] = True
            dir = [[1, 0], [0, 1], [0, -1], [-1, 0]]
            for d in dir:
                dfs(x + d[0], y + d[1], visited)

        def countIslands():
            cnt = 0
            visited = [[False] * n for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    if visited[i][j] == False and grid[i][j] == 1:
                        cnt += 1
                        dfs(i, j, visited)
            print(cnt)
            return cnt

        if countIslands() != 1:  # already disconnected
            return 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    grid[i][j] = 0
                    cnt = countIslands()
                    if cnt != 1:
                        return 1
                    grid[i][j] = 1

        return 2