[백준] #21610 마법사 상어와 비바라기(python)

📌문제

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 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부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

1. 모든 구름이 di 방향으로 si칸 이동한다.

2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.

3. 구름이 모두 사라진다.

4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.

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

5. 바구니에 저장된 물의 양이 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

예제 출력1

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

예제 출력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

예제 출력3

2657

백준 22610번 문제

💡Idea

마법사 상어🦈의 비바라기 마법 연습 과정을 그대로 구현하면 되는 문제입니다🧙‍♂️🔮

저는 문제를 푸는 과정에서 아래의 두 가지를 열심히 고려해보았습니다.

1. 1번 행과 N번 행, 1번 열과 N번 열이 연결되어 있으므로 구름의 이동 시 적절한 연산식을 만들어주자!
   $\;$
2. 자칫하면 시간 초과가 발생하니 시간을 줄여줄 수 있는 방법들을 생각하자!

고려한 점 1

우선, 현재 좌표에서 입력된 d방향으로 s만큼 이동해주면 됩니다.

$x + (s * d)$

하지만, 위의 식으로 계산된 좌표가 격자의 범위를 넘어서는 경우가 있을 수 있습니다. 이 경우, 아래와 같이 mapping을 해주어야 합니다.

s * d를 더해준 값	실제 좌표의 값
5	0
6	1
7	2
8	3
9	4

위의 표를 만족하는 연산식은 아래와 같습니다.

$(x + (s * d)) \;mod\; N$

하지만, 이동한 좌표가 음수가 되는 경우도 있습니다. 그런 경우에는 아래와 같이 mapping 해줄 수 있도록 해야 합니다.

s * d를 더한 뒤 N으로 나눈 나머지 값	실제 좌표의 값
-9	1
-8	2
-7	3
-6	4
-5	0
-4	1
-3	2
-2	3
-1	4

위의 표를 만족하는 연산식은 아래와 같습니다.

$x + ((s \;mod \;N) \;* \;d) + N) \;mod\; N$

위 연산식은 현재의 좌표에, 이동해야 하는 방향으로 $s \;mod \;N$만큼 이동하고, N을 더해준 뒤, 다시 N으로 나머지 연산을 해주는 식입니다.

저는 그래서 처음에 구름을 이동시킬 때 위와 같은 복잡한 연산식을 사용했었습니다.

하지만, 파이썬에서 제공하는 음수의 나눗셈 연산을 사용하면 $(x + (s *d)) \;mod\; N$ 식으로도 위 표와 같은 결과를 만들어낼 수 있다는 것을 뒤늦게 알게 되었습니다🤦‍♀️

따라서 그냥 아래와 같은 식을 사용하시면 됩니다!

$(x + (s * d)) \;mod\; N$

고려한 점 2

2번의 경우 list 대신 set을 사용해주었습니다.

문제의 5번에 새로 구름이 만들어질 때, 바로 직전에 구름이 있었던 칸에서는 만들어지면 안된다는 조건이 있습니다.

따라서 현재 칸이 직전의 구름의 위치를 저장하는 리스트에 있는지를 확인하기 위해서 find 연산이 이루어져야 하는데 제 경우 list를 사용하면 시간초과가 났습니다.

따라서, find의 연산의 시간복잡도가 $O(1)$인 set를 사용해서 시간을 단축하고자 하였습니다.

💻코드

• pypy3로 제출한 코드입니다
• ⏰ 시간 : 496 ms / 메모리 : 116812 KB

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
ds = [list(map(int, input().split())) for _ in range(M)]

clouds = [[N - 1, 0], [N - 1, 1], [N - 2, 0], [N - 2, 1]] # 0-base
pos = [[0, 0], [0, -1], [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1]]

for i in range(M):
    d, s = ds[i]
    
    # 1. 구름의 이동
    clouds = [((x + (s * pos[d][0])) % N, (y + (s * pos[d][1])) % N) for x, y in clouds]
    
    # 2. 구름이 있는 위치 물 1 증가
    for x, y in clouds:
        A[x][y] += 1
    
    # 4. 물복사버그
    for x, y in clouds:
        for j in range(2, 10, 2):
            nx, ny = x + pos[j][0], y + pos[j][1]
            if 0 <= nx < N and 0 <= ny < N and A[nx][ny] > 0:
                A[x][y] += 1
    
    # 5. 구름이 새로 생김
    new_clouds = set()
    for j in range(N):
        for k in range(N):
            if A[j][k] >= 2 and (j, k) not in clouds:
                new_clouds.add((j, k))
                A[j][k] -= 2
    clouds = new_clouds

print(sum([sum(x) for x in A]))

📝코드 설명

변수

• A : N X N 격자의 각 칸에 있는 물의 양을 저장하는 리스트
• ds : 이동의 정보 di와 si가 순서대로 저장되어 있는 리스트
• clouds : 현재 구름이 있는 위치를 저장하는 집합
• pos : 상하좌우와 4개의 대각선 방향으로 이동할 수 있는 좌표의 리스트로, 문제에서 주어진 숫자와 방향이 index로 똑같이 mapping되어 있다.

1. 구름의 이동

각 구름들의 이동한 뒤의 좌표를 구하기 위해서 이동방향으로 s만큼 이동하고, 좌표 밖의 인덱스 값이 나오는 경우를 처리하기 위하여 N으로 나누어주는 연산을 진행하였습니다.

2. 구름이 있는 위치 물 1 증가

현재 구름의 위치에 대해서 A의 값을 1씩 증가해주었습니다.

3. 구름 제거

구름이 사라지는 부분은, 나중에 5번 구름이 새로 생기는 경우 이전 구름들의 위치가 필요하고 새로 생긴 구름들의 위치로 값을 변경해주므로 따로 구현하지 않았습니다.

4. 물복사버그

pos의 짝수번째에 있는 값들이 대각선을 의미하는 값입니다.

pos의 짝수번째 값들에 접근하여, 대각선에 유효한 좌표가 있고 물이 존재하는 칸인지를 확인합니다.
대각선에 물이 존재할 때마다 현재 칸A의 값을 1씩 증가해줍니다.

5. 새로운 구름의 생성

A의 값을 확인하며, 물의 양이 2 이상이고 해당 인덱스가 clouds에 없다면 new_clouds에 위치를 추가해줍니다.

구름이 새로 다 만들어지면 clouds를 new_clouds로 대체해줍니다.