[백준: Python] 21610 - 마법사 상어와 비바라기

[문제]

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

어려울 거 없는 구현 및 시뮬레이션 문제입니다. 문제에서 제시한 대로 순서대로 코드를 작성하면 되겠습니다. 구현 시 주의할 점은 주어진 격자의 양 끝이 연결되어 있는 구조라는 것입니다. 즉 0열에서 왼쪽으로 이동하면 n-1열로 이동할 수 있고 이는 반대의 경우도 가능하며 행에도 적용됩니다.

순환 구조의 격자

---

[초기화]

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

격자와 이동 정보를 입력받습니다. 이후 1번 및 4번 구현을 위한 방향 벡터를 정의합니다.

---

[풀이]

    def create_cloud(self):
        return [(self.n - 1, 0), (self.n - 1, 1), (self.n - 2, 0), (self.n - 2, 1)]

문제에 제시된 대로 주어진 위치에 초기 비구름을 생성하는 메서드를 정의합니다.

    def move_cloud(self, clouds: list, d, s):
        result = set()  # 이동 및 비내리기가 끝난 구름들을 저장할 자료 구조

        dy, dx = self.move_directions[d - 1]
        my = dy * s
        mx = dx * s
        while clouds:  # 현재 구름들 기준
            y, x = clouds.pop()  # 자연스럽게 구름 제거
            y = (y + my) % self.n  # 경계를 넘을 때 돌아오기 위함
            x = (x + mx) % self.n
            self.grid[y][x] += 1
            result.add((y, x))

        return result

1번 구현 사항입니다.

1. 이동이 끝난 비구름들의 좌표를 저장하기 위한 자료구조를 정의합니다.
   • 시간복잡도 측면에서 리스트가 아닌 집합을 사용합니다.
   • 집합은 해시 가능한 자료구조로 탐색 시, O(1)의 시간 복잡도를 가지게 됩니다.
2. 이동 거리를 미리 계산에 한 번에 처리합니다.
3. 현재 비구름들을 하나씩 처리해 이동시킨 후, 해당 위치의 물의 양을 증가시킵니다.(2번 구현 사항)
   • 이동시킨 구름을 제거되어야 하기 때문에 해당 메서드에서 처리합니다.(3번 구현 사항)
   • 음수 인덱스를 생각하기 까다로울 수 있는데 다음과 같이 계산할 수 있습니다.
     • a(나누어지는 수) = b(나누는 수) × q(몫) + r(나머지)
       
       • r = -9 -(-10) = 1
       • -9 = 5 × -2 + 1
     • -9 % 5 = 1
       • -9에서 5씩 이동하면 0을 넘는 최초의 지점은 1
     • -7 % 3 = 2
       • -7에서 3씩 이동하면 0을 넘는 최초의 지점은 2
4. 이동이 끝난 비구름의 좌표를 저장합니다.
5. 모든 비구름에 대한 처리가 끝나면 이동이 끝난 좌표 리스트를 반환합니다.

    def copy_water(self, result):
        for y, x in result:  # 물복사 버그
            cnt = 0
            for dy, dx in self.water_directions:
                my = y + dy
                mx = x + dx
                if 0 <= my < self.n and 0 <= mx < self.n and self.grid[my][mx] != 0:
                    cnt += 1
            self.grid[y][x] += cnt

4번 구현 사항입니다. 1번 구현 사항에서 이동이 끝난 비구름의 좌표를 매개변수로 받습니다.

1. 비구름마다 물 바구니를 계산하기 위한 변수를 초기화합니다.
2. 비구름들의 대각선을 계산합니다.
3. 계산된 대각선에 해당하는 격자의 값이 0이 아니라면 물이 있다는 것이므로 카운트합니다.
4. 카운트된 값만큼 바구니의 값을 갱신합니다.

    def make_clouds(self, clouds, result):
        for y in range(self.n):
            for x in range(self.n):
                if (y, x) not in result and self.grid[y][x] >= 2:
                    self.grid[y][x] -= 2
                    clouds.append((y, x))

5번 구현 사항입니다. 1번 구현 사항에서 반환된 결과를 마찬가지로 매개변수로 받습니다. 또한 만들어진 비구름들을 저장하기 위해 기존에 만들었던 비구름을 저장하는 자료구조 또한 매개변수로 받습니다.

 

격자를 돌며 새로운 비구름이 만들어지지 않으면서 비구름을 만들 수 있는 바구니를 탐색합니다.

    def count_water(self):
        return sum(map(sum, self.grid))

모든 연산이 끝난 후, 바구니의 값들을 합산합니다.

    def solve(self):
        clouds = self.create_cloud()  # 구름 생성

        for d, s in self.move_info:
            result = self.move_cloud(clouds, d, s)  # 구름 이동
            self.copy_water(result)  # 비복사
            self.make_clouds(clouds, result)  # 새로운 비구름 생성

        print(self.count_water())

위에서 정의한 메서드들을 순차적으로 실행시킵니다.

---

[전체 코드]

import sys
input = lambda: sys.stdin.readline()


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.move_info = [tuple(map(int, input().split())) for _ in range(self.m)]
        self.move_directions = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]
        self.water_directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]

    def create_cloud(self):
        return [(self.n - 1, 0), (self.n - 1, 1), (self.n - 2, 0), (self.n - 2, 1)]

    def move_cloud(self, clouds: list, d, s):
        result = set()  # 이동 및 비내리기가 끝난 구름들을 저장할 자료 구조

        dy, dx = self.move_directions[d - 1]
        my = dy * s
        mx = dx * s
        while clouds:  # 현재 구름들 기준
            y, x = clouds.pop()  # 자연스럽게 구름 제거
            y = (y + my) % self.n  # 경계를 넘을 때 돌아오기 위함
            x = (x + mx) % self.n
            self.grid[y][x] += 1
            result.add((y, x))

        return result

    def copy_water(self, result):
        for y, x in result:  # 물복사 버그
            cnt = 0
            for dy, dx in self.water_directions:
                my = y + dy
                mx = x + dx
                if 0 <= my < self.n and 0 <= mx < self.n and self.grid[my][mx] != 0:
                    cnt += 1
            self.grid[y][x] += cnt

    def make_clouds(self, clouds, result):
        for y in range(self.n):
            for x in range(self.n):
                if (y, x) not in result and self.grid[y][x] >= 2:
                    self.grid[y][x] -= 2
                    clouds.append((y, x))

    def count_water(self):
        return sum(map(sum, self.grid))

    def solve(self):
        clouds = self.create_cloud()  # 구름 생성

        for d, s in self.move_info:
            result = self.move_cloud(clouds, d, s)  # 구름 이동
            self.copy_water(result)  # 비복사
            self.make_clouds(clouds, result)  # 새로운 비구름 생성

        print(self.count_water())


problem = Main()
problem.solve()

---