> For the complete documentation index, see [llms.txt](https://70825.gitbook.io/koala_basic_study_5th/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://70825.gitbook.io/koala_basic_study_5th/end/2/4.md).

# BOJ 21610 - 마법사 상어와 비바라기

## BOJ 21610 - 마법사 상어와 비바라기

{% embed url="<https://www.acmicpc.net/problem/21610>" %}

가장 최근에 나온 역량 테스트 문제 중에 하나인 마법사 상어와 비바리기 입니다.

바구니에 물이 있고, 처음에 비구름이 4개 설정되는데 본문에 있는 과정을 거쳐서 모두 끝난 뒤에 물의 양을 구하라는 문제입니다.

이 문제는 5번의 과정을 통해 문제를 풀려고 합니다.

1. 입력값 받기
2. 구름 이동하기
3. 물 복사 버그
4. 구름 생성하기
5. 물의 양의 합 구하고 출력하기

### 1. 입력값 받기

d와 s를 입력 받는 것은 for문 안에서 m번 입력받으면 됩니다.

```python
n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))

for t in range(m):
    d, s = map(int,input().split())
```

### 2. 구름 이동하기

우리는 구름을 이동해야 하므로 deque를 이용하여 처음 값들을 넣어줍니다.

```python
from collections import deque

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
```

그리고 8방향으로 이동해야 하므로 dx와 dy 배열도 본문 방향에 맞게 추가합니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
```

구름이 이동하기 전에 본문 과정 5번을 보면 구름이 사라진 곳에서는 구름이 생기지 말아야 한다고 합니다. 그래서 cq = deque()를 만들어서 구름이 이동하면 좌표를 cq에 넣어줍니다.

그리고 이제 while q를 이용하여 q에 있는 값을 빼고 하나씩 이동해주면 됩니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()
    
    while q:
        x, y = q.popleft()
```

여기서 구름을 이동할 때, d방향으로 s칸을 1칸씩 s번 이동하면 시간이 오래 걸릴 것 같습니다. 그러므로 한 번에 이동할 방법을 생각해봐야 합니다.

일단 이동하는 거리는 아래와 같다는 것을 알 것 입니다.

* nx = x + dx\[d-1]\*s
* ny = y + dy\[d-1]\*s

문제는 nx와 ny값이 음수가 나올 수 있다는 것인데요. 여기서 100 \* n이라는 큰 값을 추가해서 nx, ny에 더해줘서 무조건 양수가 나오도록 해주고, n으로 나눈 나머지로 값을 수정해주면 됩니다.

* nx = (100 \* n + x + dx\[d-1]\*s) % n
* ny = (100 \* n + y + dy\[d-1]\*s) % n

{% hint style="info" %}
100 \* n이 들어가는 이유는 n의 나머지를 구할 때, n의 배수를 넣어줘야 값에 영향이 없기 때문입니다. 이 내용은 정수론 내용이므로 그냥 '음수가 나올 수 있는 경우에는 큰 수를 넣어서 양수로 만들어주고 n의 나머지로 값을 설정하는데, 이때 답에 영향이 없으려면 큰 수는 n의 배수여야 하구나' 라고 이해하고 넘어가시면 됩니다.

예를 들어 n = 7이고, (6, 6)의 구름이 (5, 5)로 이동할 때, 단순히 100을 더해주면 (106, 106)에서 (105, 105)가 됩니다.  105는  7로 나누어 떨어지기 때문에 % 7을 해주면 (105, 105)는 (0, 0)이 되서 (5, 5) 이동하는 것이 아니게 됩니다.

하지만 100이 아닌 7의 배수인 105를 넣어주면 (111, 111)에서 (110, 110)이 되는데 110 % 7 = 5이므로 (5, 5)가 나오게 됩니다.
{% endhint %}

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()

    while q:
        x, y = q.popleft()
        nx, ny = (100 * n + x + dx[d - 1] * s) % n, (100 * n + y + dy[d - 1] * s) % n
```

이제 구름이 이동했으므로 구름이 이동한 곳 좌표의 바구니에 1을 추가하고, cq에 (nx, ny)를 추가하면 됩니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()

    while q:
        x, y = q.popleft()
        nx, ny = (100 * n + x + dx[d - 1] * s) % n, (100 * n + y + dy[d - 1] * s) % n
        arr[nx][ny] += 1
        cq.append((nx, ny))
```

본문 과정 5에서 새로운 구름을 만들 때, 구름이 사라진 곳에서 구름을 만들지 말아야 하므로 not\_cloud라는 리스트 변수를 만들어서 값을 list(cq)로 설정해주면 됩니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()

    while q:
        x, y = q.popleft()
        nx, ny = (100 * n + x + dx[d - 1] * s) % n, (100 * n + y + dy[d - 1] * s) % n
        arr[nx][ny] += 1
        cq.append((nx, ny))
    not_cloud = list(cq)
```

### 3. 물 복사 버그

각 구름이 이동한 좌표에서 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니 수만큼 물의 양을 넣어주라고 합니다.

그래서 먼저 대각선으로 이동해주는 배열인 kx, ky를 추가합니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]
kx,ky = [-1, -1, 1, 1], [-1, 1, -1, 1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()

    while q:
        x, y = q.popleft()
        nx, ny = (100 * n + x + dx[d - 1] * s) % n, (100 * n + y + dy[d - 1] * s) % n
        arr[nx][ny] += 1
        cq.append((nx, ny))
    not_cloud = list(cq)
```

그리고 이제 cq를 이용하여 cq에 있는 값을 (x, y)로 뽑고, (x, y) 기준으로 대각선에 있는 바구니들이 물이 있으면 개당 arr\[x]\[y] += 1을 해주면 됩니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]
kx,ky = [-1, -1, 1, 1], [-1, 1, -1, 1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()

    while q:
        x, y = q.popleft()
        nx, ny = (100 * n + x + dx[d - 1] * s) % n, (100 * n + y + dy[d - 1] * s) % n
        arr[nx][ny] += 1
        cq.append((nx, ny))
    not_cloud = list(cq)
    
    while cq:
        x, y = cq.popleft()
        for i in range(4):
            nx, ny = x + kx[i], y + ky[i]
            if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > 0:
                arr[x][y] += 1
```

### 4. 구름 생성하기

2중 for문을 이용하여 arr\[x]\[y] >= 2이고, not\_cloud에 속하지 않는 좌표이면 arr\[x]\[y] -= 2를 해주고, q에 (x, y)를 추가하면 됩니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]
kx,ky = [-1, -1, 1, 1], [-1, 1, -1, 1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()

    while q:
        x, y = q.popleft()
        nx, ny = (100 * n + x + dx[d - 1] * s) % n, (100 * n + y + dy[d - 1] * s) % n
        arr[nx][ny] += 1
        cq.append((nx, ny))
    not_cloud = list(cq)

    while cq:
        x, y = cq.popleft()
        for i in range(4):
            nx, ny = x + kx[i], y + ky[i]
            if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > 0:
                arr[x][y] += 1

    for x in range(n):
        for y in range(n):
            if arr[x][y] >= 2 and (x, y) not in not_cloud:
                q.append((x, y))
                arr[x][y] -= 2
```

### 5. 물의 양의 합을 구하고 출력하기

이 기능은 단순히 2중 for문을 이용하여 arr\[x]\[y]의 값을 모두 더해주고 출력해주면 됩니다.

```python
from collections import deque
dx,dy = [0,-1,-1,-1,0,1,1,1], [-1, -1, 0, 1, 1, 1, 0, -1]
kx,ky = [-1, -1, 1, 1], [-1, 1, -1, 1]

n, m = map(int,input().split())
arr = list(list(map(int,input().split())) for _ in range(n))
q = deque([(n-1,0), (n-1,1), (n-2,0), (n-2,1)])

for t in range(m):
    d, s = map(int,input().split())
    cq = deque()

    while q:
        x, y = q.popleft()
        nx, ny = (100 * n + x + dx[d - 1] * s) % n, (100 * n + y + dy[d - 1] * s) % n
        arr[nx][ny] += 1
        cq.append((nx, ny))
    not_cloud = list(cq)

    while cq:
        x, y = cq.popleft()
        for i in range(4):
            nx, ny = x + kx[i], y + ky[i]
            if 0 <= nx < n and 0 <= ny < n and arr[nx][ny] > 0:
                arr[x][y] += 1

    for x in range(n):
        for y in range(n):
            if arr[x][y] >= 2 and (x, y) not in not_cloud:
                q.append((x, y))
                arr[x][y] -= 2

ans = 0
for x in range(n):
    for y in range(n):
        ans += arr[x][y]
print(ans)
```