[백준: Python] 2638 - 치즈

[문제]

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

시뮬레이션이 포함된 그래프 탐색 문제입니다. 주요 전략은 치즈의 외부와 내부 공간을 분리하여, 치즈의 외부를 지속적으로 탐색하는 것입니다.

---

[초기화]

    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.grid = [list(map(int, input().split())) for _ in range(self.n)]
        self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        self.answer = 0

탐색은 BFS, DFS 둘 다 가능하지만, BFS가 더 빠른 속도를 보장할 수 있습니다.

---

[풀이]

    def count_cheese(self):
        return sum(sum(i) for i in self.grid)

최초 1회 실행하는 메서드로, 맵에 주어진 치즈의 총개수를 계산합니다. 이때 계산된 치즈의 수가 0이 될 때까지 탐색을 진행합니다.

    def split_space(self):
        dq = deque([(0, 0)])
        visited = [[False] * self.m for _ in range(self.n)]

        while dq:
            y, x = dq.popleft()

            for dy, dx in self.directions:
                my = y + dy
                mx = x + dx
                if 0 <= my < self.n and 0 <= mx < self.m and not visited[my][mx] and self.grid[my][mx] != 1:
                    visited[my][mx] = True
                    self.grid[my][mx] = 10
                    dq.append((my, mx))

치즈의 내부와 외부를 분리합니다. 좌측 상단인 부분에서부터 치즈가 아닌 곳들을 전부 탐색합니다.

 

시작위치가 고정인 이유는, 치즈의 모양이 시간이 지날 수록 변동이 되는 것도 있지만, 무엇보다 문제에서 맨 가장자리에는 치즈가 없다는 전제 조건을 걸었기 때문입니다.

 

치즈가 아닌 값(0, 10)을 탐색하는 이유는 처음 0인 공간을 모두 탐색하면서 치즈의 외부는 10, 내부는 0으로 구분 짓고, 치즈가 녹아 내부와 외부의 경계가 무너졌을 때, 탐색을 이어나가야 하기 때문입니다.

 

외부를 구분하는 값은 10이 아니어도 됩니다. 저는 디버깅 과정에서 보기 편한 값이 10이어서 선택했습니다.

    def melt(self):
        dq = deque([(0, 0)])
        visited = [[False] * self.m for _ in range(self.n)]
        cheese = []  # 발견한 치즈를 저장
        melted_cheese = []  # 녹일 치즈를 저장
        
        while dq:
            y, x = dq.popleft()

            for dy, dx in self.directions:
                my = y + dy
                mx = x + dx
                if 0 <= my < self.n and 0 <= mx < self.m and not visited[my][mx]:
                    visited[my][mx] = True
                    if self.grid[my][mx] == 10:
                        dq.append((my, mx))
                    else:
                        cheese.append((my, mx))

        while cheese:
            y, x = cheese.pop()
            space = 0

            for dy, dx in self.directions:
                my = y + dy
                mx = x + dx

                if 0 <= my < self.n and 0 <= mx < self.m and self.grid[my][mx] == 10:
                    space += 1
                    if space == 2:
                        melted_cheese.append((y, x))
                        break

        for y, x in melted_cheese:  # 치즈를 발견하는 과정에서 바로 녹이면 빈 공간이 되면서 다른 치즈에 영향을 줌
            self.grid[y][x] = 10
            
        return len(melted_cheese)  # 녹인 치즈의 수 반환

공간을 분리하는 코드와 동일하지만, 치즈를 녹이는 로직이 추가되어 있습니다.

1. 외부에 노출된 치즈들만 녹여야 하므로, 외부 공간 탐색
   • 치즈를 만나면 나중에 녹여야 하므로 따로 저장
2. 외부 탐색이 모두 끝났다면 모아둔 치즈를 확인
   • 치즈를 하나씩 꺼내, 상하좌우를 확인한 후, 접하는 빈공간의 수를 계산
   • 공간이 2가되면 녹일 치즈이므로 다시 한번 따로 저장
   • 녹일 치즈로 확정이 됐으면 다음 검사는 할 필요 없으므로 종료
3. 녹일 치즈들의 값을 빈공간으로 변경
   • 녹일 치즈를 탐색할 때, 값을 바로 변경하지 않고 모아뒀다가 일괄적으로 변경하는 이유는 다음 치즈에 영향을 받기 때문
   • 쉽게 말해 현재 치즈를 녹여서 빈 공간으로 만들어버리면, 해당 치즈와 접한 치즈들은 접하는 빈 공간이 하나 늘어나므로 현재 녹을 치즈가 아닌데, 녹아버리는 상황이 발생
   • 혹은 간단하게 생각한다면, 치즈는 동시에 녹아내리므로 이를 구현하고자 하는 의도도 존재
4. 녹인 치즈의 수 반환

    def solve(self):
        rest_cheese = self.count_cheese()

        while rest_cheese:
            self.split_space()  # 내부 외부 공간 구분
            rest_cheese -= self.melt()

            self.answer += 1

        print(self.answer)

1. 초기 치즈의 수 계산
2. 계산된 치즈가 모두 녹을 때 까지 메서드 반복
   1. 현재 상태에서 내부와 외부 분리
   2. 분리된 공간을 바탕으로 치즈를 녹임
   3. 녹은 치즈의 수를 반환받아 감소
   4. 치즈를 한 차례 녹였으므로 정답 갱신

---

[전체 코드]

from collections import deque


class Main:
    def __init__(self):
        self.n, self.m = map(int, input().split())
        self.grid = [list(map(int, input().split())) for _ in range(self.n)]
        self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        self.answer = 0

    def count_cheese(self):
        return sum(sum(i) for i in self.grid)

    def split_space(self):
        dq = deque([(0, 0)])
        visited = [[False] * self.m for _ in range(self.n)]

        while dq:
            y, x = dq.popleft()

            for dy, dx in self.directions:
                my = y + dy
                mx = x + dx
                if 0 <= my < self.n and 0 <= mx < self.m and not visited[my][mx] and self.grid[my][mx] != 1:
                    visited[my][mx] = True
                    self.grid[my][mx] = 10
                    dq.append((my, mx))

    def melt(self):
        dq = deque([(0, 0)])
        visited = [[False] * self.m for _ in range(self.n)]
        cheese = []  # 발견한 치즈를 저장
        melted_cheese = []  # 녹일 치즈를 저장
        
        while dq:
            y, x = dq.popleft()

            for dy, dx in self.directions:
                my = y + dy
                mx = x + dx
                if 0 <= my < self.n and 0 <= mx < self.m and not visited[my][mx]:
                    visited[my][mx] = True
                    if self.grid[my][mx] == 10:
                        dq.append((my, mx))
                    else:
                        cheese.append((my, mx))

        while cheese:
            y, x = cheese.pop()
            space = 0

            for dy, dx in self.directions:
                my = y + dy
                mx = x + dx

                if 0 <= my < self.n and 0 <= mx < self.m and self.grid[my][mx] == 10:
                    space += 1
                    if space >= 2:
                        melted_cheese.append((y, x))
                        break

        for y, x in melted_cheese:  # 치즈를 발견하는 과정에서 바로 녹이면 빈 공간이 되면서 다른 치즈에 영향을 줌
            self.grid[y][x] = 10
            
        return len(melted_cheese)  # 녹인 치즈의 수 반환

    def solve(self):
        rest_cheese = self.count_cheese()

        while rest_cheese:
            self.split_space()  # 내부 외부 공간 구분
            rest_cheese -= self.melt()

            self.answer += 1

        print(self.answer)


problem = Main()
problem.solve()

---