[백준 21610] 마법사 상어와 비바라기(Python 풀이)

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

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

---

이 문제는 골드 5 난이도의 구현 문제입니다.

문제에서 제시한 방향대로 코드를 구현한다면 쉽게 풀릴 내용이지만 다음 내용만 조심하면 될 것 같습니다.

이어진 격자

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

즉, 배열이 이어져 있다는 것입니다. 배열의 마지막 원소의 다음 원소는 첫 번째 원소가 됩니다. 따라서 구름을 d방향으로 s만큼 이동하는 경우 다음과 같이 모듈러 연산(%)를 이용하여 적절한 위치로 이동해야 합니다.

ny = (y + dy8[d] * s) % N 
nx = (x + dx8[d] * s) % N

 

물복사 버그에서의 격자 경계

4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.

구현의 4번째 단계에서 격자 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아닙니다. 따라서 이 경우에는 구름이 이동할 때와 달리 다음과 같이 예외처리를 해줘야 합니다.

for y, x in moved_clouds:
    # 이동한 구름들의 대각 4방향을 조사하여 count만큼 물의 양 추가
    cnt = 0
    for d in range(4):
        ny = y + dy4[d]
        nx = x + dx4[d]
        # 이 때는 구름의 대각선 거리가 1이 아니므로 예외처리
        if ny < 0 or nx < 0 or ny >= N or nx >= N:
            continue
        elif board[ny][nx] > 0:
            cnt += 1

---

전체 소스 코드

# 입력
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
moves = [tuple(map(int, input().split())) for _ in range(M)]
 
# 8방향
dy8 = ("empty", 0, -1, -1, -1, 0, 1, 1, 1)
dx8 = ("empty", -1, -1, 0, 1, 1, 1, 0, -1)
 
# 대각 4방향
dy4 = (-1, -1,  1, 1)
dx4 = (-1,  1, -1, 1)
 
clouds = [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)] # 구름 좌표
for d, s in moves:
    # 모든 구름 이동
    moved_clouds = []
    for y, x in clouds:
        # 구름들을 d 방향으로 s만큼 이동(구름의 좌표는 연결되어있으므로 %N)
        ny = (y + dy8[d] * s) % N 
        nx = (x + dx8[d] * s) % N
        board[ny][nx] += 1 # 물의 양 추가
        moved_clouds.append((ny, nx)) # 이동한 구름 좌표에 추가
 
    for y, x in moved_clouds:
        # 이동한 구름들의 대각 4방향을 조사하여 count만큼 물의 양 추가    
        cnt = 0
        for d in range(4):
            ny = y + dy4[d]
            nx = x + dx4[d]
            # 이 때는 구름의 좌표가 연결되어 있지 않으므로 예외처리)
            if ny < 0 or nx < 0 or ny >= N or nx >= N: continue
            elif board[ny][nx] > 0: cnt += 1
        board[y][x] += cnt
 
    new_clouds = []
    for y in range(N):
        for x in range(N):
            # 이동한 구름의 좌표와 동일하지 않고, 물의 양이 2 이상인 경우
            if (y, x) in moved_clouds or board[y][x] < 2:
                continue
            # 물을 2만큼 소비하고 새로운 구름 배열(new_clouds)에 추가
            board[y][x] -= 2
            new_clouds.append((y, x))
    clouds = new_clouds # 다음 loop에서 사용할 clouds 배열을 new_clouds로 교체
 
# 물의 양 합 계산 후 출력
result = 0
for y in range(N):
    for x in range(N):
        result += board[y][x]
print(result)