[BOJ][🟡5][백준#21610] 마법사 상어와 비바라기

문제 출처

BAEKJOON Online Judge #21610

문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다. 비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

모든 구름이 di 방향으로 si칸 이동한다. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다. 구름이 모두 사라진다. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.

이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다. 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.

바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

입력

첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다. 다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

출력

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

제한

2 ≤ N ≤ 50 1 ≤ M ≤ 100 0 ≤ A[r][c] ≤ 100 1 ≤ di ≤ 8 1 ≤ si ≤ 50

예제

예제 1

입력

5 4
0 0 1 0 2
2 3 2 1 0
4 3 2 9 0
1 0 2 9 0
8 8 2 1 0
1 3
3 4
8 1
4 8

출력

77

예제 2

입력

5 8
0 0 1 0 2
2 3 2 1 0
0 0 2 0 0
1 0 2 0 0
0 0 2 1 0
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2

출력

41

예제 3

입력

5 8
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
100 100 100 100 100
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 1

출력

2657

My Sol

def main():
    def move():
        d, s = map(int, input().split())
        di, dj = DD[d]
        for i in range(len(clouds)):
            ci, cj = clouds[i]
            si = check_over(ci+di*s)
            sj = check_over(cj+dj*s)
            clouds[i] = (si, sj)

    def check_over(n):
        while n < 0: n += N
        while n >= N: n -= N
        return n

    def rain():
        for ci, cj in clouds:
            mat[ci][cj] += 1

    def copy_water():
        for ci, cj in clouds:
            cnt_around = count_around(ci, cj)
            mat[ci][cj] += cnt_around

    def count_around(i, j):
        cnt_around = 0
        for di, dj in ((-1,-1),(-1,1),(1,-1),(1,1)):
            si, sj = i+di, j+dj
            if not (0<=si<N and 0<=sj<N): continue
            if not mat[si][sj]: continue
            cnt_around += 1
        return cnt_around

    def make_cloud(clouds):
        new_clouds = []
        clouds_set = set(clouds)
        for i in range(N):
            for j in range(N):
                if (i, j) in clouds_set: continue
                if mat[i][j] < 2: continue
                mat[i][j] -= 2
                new_clouds.append((i, j))
        return new_clouds

    def count_mat():
        cnt = 0
        for i in range(N):
            for j in range(N):
                cnt += mat[i][j]
        return cnt

    N, M = map(int, input().split())
    DD = [(0,0),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1)]
    mat = [list(map(int, input().split())) for _ in range(N)]
    clouds = [(N-1,0),(N-1,1),(N-2,0),(N-2,1)]
    for _ in range(M):
        move()
        rain()
        copy_water()
        clouds = make_cloud(clouds)
    return count_mat()

print(main())

나름 빡빡한 구현이 필요한 문제였지만 단계적으로 접근하면 쉽게 해결할 수 있는 문제였다. 함수의 역할을 구분하여 철저하게 작은 단위로 잘라 작성했다.

1. 입력을 받아 2차원 배열 mat을 만든다. 물의 양을 기록하는 격자가 될 것이다.
2. 최초의 구름은 왼쪽 하단 2x2 크기의 구름이므로 clouds 변수를 두어 구름의 각 좌표를 저장한다.
3. M회의 반복을 하는 것을 염두에 두고 for문을 둔다.
4. 구름을 이동시키는 move 함수를 작성한다. 이동 방향과 이동 거리를 입력 받고, 해당 이동방향 인덱스를 DD 배열에서 찾아 di, dj를 구한다.
5. clouds 내부 좌표들마다 이동시킨 뒤, 범위를 벗어난다면 범위 내로 좌표를 재조정하는 함수 check_over를 만들어 좌표를 재조정 처리하여 clouds 변수의 각 좌표를 처리한다. 즉, 구름을 옮기는 것이다.
6. 생성된 구름마다 비를 내려 mat의 각 좌표에 1을 추가하는 함수 rain을 작성한다.
7. 물 복사를 하는 copy_water 함수를 작성한다. 구름의 각 좌표마다 주변을 확인하는 함수 count_around 함수를 작성하여 대각선 4개의 좌표로부터 추가할 바구니의 물의 양을 계산하여 추가한다.
8. count_around 함수는 격자를 벗어나거나 값이 없으면 카운트를 추가하지 않으므로 2가지 상황을 제외한 나머지에서는 카운트를 추가한다. 이를 4개 좌표 모두 확인하여 반환한다.
9. 구름을 다시 만드는 함수 make_cloud 함수를 작성한다. NxN의 전체 좌표를 모두 완전탐색하는데, 문제 조건 중 기존에 구름이 사라진, 즉 clouds에 있는 좌표에서는 구름이 생기면 안 되기 때문에 이를 확인한다. 이 중 2가 넘는 모든 칸을 new_clouds에 담은 뒤, 모든 완전탐색을 마치면 이를 반환한다.
10. main 함수 내의 clouds를 위의 new_clouds로 대체한다. 이를 M회 반복한다.
11. 모든 반복을 처리한 mat의 각 좌표의 값을 모두 누적해 반환하는 함수 count_mat을 작성한다.
12. main 함수의 return값을 출력한다.

결과

맞았습니다!!