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

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

21610번: 마법사 상어와 비바라기Baekjoon Online Judge

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

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

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

1. 입력값 받기

2. 구름 이동하기

3. 물 복사 버그

4. 구름 생성하기

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

1. 입력값 받기

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

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를 이용하여 처음 값들을 넣어줍니다.

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 배열도 본문 방향에 맞게 추가합니다.

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에 있는 값을 빼고 하나씩 이동해주면 됩니다.

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

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)가 나오게 됩니다.

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)를 추가하면 됩니다.

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)로 설정해주면 됩니다.

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를 추가합니다.

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을 해주면 됩니다.

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)를 추가하면 됩니다.

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]의 값을 모두 더해주고 출력해주면 됩니다.

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)