[백준 2024/09/20] 2573번 빙산

1. 문제

https://www.acmicpc.net/problem/2573

빙산 정복 기념 그림 호호~

 

2. 접근 방법

 

 

 

 

우선 얼음의 위치에 따른, 바닷물이 맞닿아 있는 개수를 base_sea라는 리스트에 저장해 주었다.

따라서, 맞닿아 있는 바다의 개수를 계산하면서, 얼음이 있는 위치를 glacier_loc이라는 deque에 저장해 주었다.

이를 통해 glacier_loc을 순환하면서, 값들을 수정할 수 있다.

이를 이용하지 않는다면, 2중 for문을 사용하게 되어 시간초과가 날 가능성이 높다.

또한 문제에서 제시하였듯, 리스트의 맨 위에 줄, 아래 줄, 그리고 왼쪽, 오른쪽 줄은 0으로 채워져 있으므로 범위를 이용할 경우가 있을 때, 1 < x < n -1 과 1 < y < m - 1을 이용해서 그나마 덜 코드를 돌릴 수 있는 방향으로 이용할 수 있다.

glacier
[0, 0, 0, 0, 0, 0, 0]
[0, 2, 4, 5, 3, 0, 0]
[0, 3, 0, 2, 5, 2, 0]
[0, 7, 6, 2, 4, 0, 0]
[0, 0, 0, 0, 0, 0, 0]

base_sea
[0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 1, 2, 0, 0]
[0, 2, 0, 1, 0, 3, 0]
[0, 2, 2, 1, 2, 0, 0]
[0, 0, 0, 0, 0, 0, 0]

 

이렇게 base_sea라는 2중 리스트를 선언해서, 맞닿아 있는 바다의 개수를 적용시켰다.

 

만약 특정 얼음 - base_sea를 하게 되었을 때, height 가 0보다 작거나 같다면 popped라는 리스트에 이를 저장해 주었다.

또한, glacier_loc에서 popleft를 하고 난 후, 다시 값을 append 해주지 않았다. 왜냐하면 이제 해당 위치는 물에 잠긴 상태이기 때문이다.

 

popped 리스트에 저장되어 있는 위치를 이용해서, base_sea에서 해당 위치 위, 아래, 왼쪽, 오른쪽에 대해서 + 1을 해주었다.

해당 위치가 pop 되면서 맞닿아 있는 바다의 개수가 +1 되었기 때문이다.

자기 자신은 다시 접근하지 않을 것이기 때문에 신경쓰지 않았다.

 

이후, 특정 얼음의 위치에서 dfs를 통해 맞닿아 있는 얼음의 개수를 세주었다. 모든 개수의 얼음이 count 되었다면, 해당 얼음들은 모두 이어져 있는 것이기 때문에, 다시 while 문을 진행할 수 있도록 하였다.

 

처음에 dfs를 재귀적으로 작성하였지만, recursion error가 발생하였다.

 

    def dfs(self, i, j, visited):
        if i < 0 or i >= self.n or j < 0 or j >= self.m or visited[i][j] or self.glacier_h[i][j] <= 0:
            return 0

        visited[i][j] = True
        return 1 + self.dfs(i - 1, j, visited) + self.dfs(i + 1, j, visited) + self.dfs(i, j - 1, visited) + self.dfs(i, j+1, visited)

 

이에, stack으로 다시 구현할 수 밖에 없었다.

 

    def dfs(self, i, j, visited):
        stack = [(i, j)]
        count = 0
        while stack:
            x, y = stack.pop()
            if x <= 0 or x >= self.n-1 or y <= 0 or y >= self.m-1 or visited[x][y] or self.glacier_h[x][y] <= 0:
                continue
            visited[x][y] = True
            count += 1
            stack.append((x - 1, y))
            stack.append((x + 1, y))
            stack.append((x, y - 1))
            stack.append((x, y + 1))
        return count

몇번 재귀에게 뒤통수를 맞고 나니,,, 그냥 항상 stack으로 구현을 시작해야 하는건가,, 라는 생각이 든다..ㅠㅠ

 

이렇게 코드를 제출하였더니, index error가 발생하였다.

따라서, 고려하지 않은 case에 대해서 생각하다가 아래의 경우를 까먹은 것을 알게 되었다.

0 0 0 0 0 0
0 1 1 1 1 0
0 1 0 0 1 0 
0 1 1 1 1 0 
0 0 0 0 0 0

 

위의 경우는 한번에 모든 glacier_loc이 pop 되기 때문에, glacier_loc이 비어 있는 deque가 되게 된다.

    def check_status(self):
        if not self.glacier_loc:
            self.all_melted = True
            return False

        i, j = self.glacier_loc[0]
        visited = [[False] * self.m for i in range(self.n)]
        #print(visited)
        glacier_size = self.dfs(i, j, visited)
        if glacier_size != self.total_ice:
            return False
        return True

 따라서, check_status 부분에서, glacier_loc이 비어있는지 확인하고 이를 self.all_melted라는 flag를 이용해서 표현해 주고 return 해 주었다.

 

왜냐하면 그 다음으로, i, j = self.glacier_loc[0] 으로 접근을 시도하게 되는데, 비어있다면 index error가 발생하게 된다.

 

3. 코드

from collections import deque


class Glacier:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.glacier_h = []
        self.base_sea = [[0] * m for _ in range(n)]
        self.glacier_loc = deque()
        self.total_ice = 0
        self.all_melted = False

    def set_base_sea(self, i, j):
        near_sea = 0
        if self.glacier_h[i-1][j] <= 0:
            near_sea += 1
        if self.glacier_h[i+1][j] <= 0:
            near_sea += 1
        if self.glacier_h[i][j-1] <= 0:
            near_sea += 1
        if self.glacier_h[i][j+1] <= 0:
            near_sea += 1

        return near_sea

    def set_glacier_h(self):
        for _ in range(self.n):
            self.glacier_h.append(list(map(int, input().split())))

        for i in range(1, self.n - 1):
            for j in range(1, self.m - 1):
                if self.glacier_h[i][j] > 0:
                    self.total_ice += 1
                    self.glacier_loc.append([i, j])
                    self.base_sea[i][j] = self.set_base_sea(i, j)

    def renew_sea_status(self, popped):
        while popped:
            x, y = popped.popleft()
            self.base_sea[x-1][y] += 1
            self.base_sea[x+1][y] += 1
            self.base_sea[x][y+1] += 1
            self.base_sea[x][y-1] += 1

    def dfs(self, i, j, visited):
        stack = [(i, j)]
        count = 0
        while stack:
            x, y = stack.pop()
            if x <= 0 or x >= self.n-1 or y <= 0 or y >= self.m-1 or visited[x][y] or self.glacier_h[x][y] <= 0:
                continue
            visited[x][y] = True
            count += 1
            stack.append((x - 1, y))
            stack.append((x + 1, y))
            stack.append((x, y - 1))
            stack.append((x, y + 1))
        return count

    def check_status(self):
        if not self.glacier_loc:
            self.all_melted = True
            return False

        i, j = self.glacier_loc[0]
        visited = [[False] * self.m for i in range(self.n)]
        glacier_size = self.dfs(i, j, visited)
        if glacier_size != self.total_ice:
            return False
        return True

    def get_years(self):
        years = 0
        while self.total_ice > 0:
            years += 1
            popped_ice = deque()
            ice_length = len(self.glacier_loc)
            for _ in range(ice_length):
                i, j = self.glacier_loc.popleft()
                self.glacier_h[i][j] -= self.base_sea[i][j]
                if self.glacier_h[i][j] <= 0:
                    popped_ice.append([i, j])
                    self.total_ice -= 1
                else:
                    self.glacier_loc.append([i, j])

            self.renew_sea_status(popped_ice)
            if not self.check_status():
                if self.all_melted:
                    return 0
                return years

        return 0


if __name__ == "__main__":
    n, m = map(int, input().split())
    glacier = Glacier(n, m)
    glacier.set_glacier_h()
    print(glacier.get_years())