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

문제

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

 

문제 풀이

 8 방향 탐색과, 대각선 4방향 탐색을 사용하여서 문제의 요구사항에 따라 그대로 구현하면 정답을 찾을 수 있다.

1. 모든 구름이 d 방향으로 s칸 만큼 이동한다.
   • 격자는 1번과 N번 열, 1행과 N번 열이 연결되어 있다.
   • 이런 조건이 나오면 모듈러(%) 연산을 활용하면 된다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 비를 내린 구름은 모두 사라진다.
4. 2에서 물이 증가한 칸(구름이 있었 던 칸)에 물복사버그 마법을 시전한다. 물복사 버그 마법은 대각선 4방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 물의 양이 증가한다.
   • 연결된 격자와 달리 범위를 벗어나는 경우는 포함하지 않는다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

 

코드

sys import stdin
from copy import deepcopy


def visitable(r, c):
    return 0 <= r < N and 0 <= c < N


def simulation(cur_d, cur_s):
    global cloud_loc
    new_cloud_loc = []

    dr, dc = [a * b for a, b in zip(move_dirs[cur_d], [cur_s, cur_s])]

    # case 1
    for r, c in cloud_loc:
        next_r, next_c = (r + dr) % N, (c + dc) % N
        # case 2
        board[next_r][next_c] += 1
        new_cloud_loc.append((next_r, next_c))

    # case 4
    for r, c in new_cloud_loc:
        for dr, dc in search_dirs:
            next_r, next_c = r + dr, c + dc

            if visitable(next_r, next_c) and board[next_r][next_c] > 0:
                board[r][c] += 1

    next_cloud_loc = []
    # case 5
    for r in range(N):
        for c in range(N):
            if board[r][c] >= 2 and (r, c) not in new_cloud_loc:
                board[r][c] -= 2
                next_cloud_loc.append((r, c))

    cloud_loc = deepcopy(next_cloud_loc)


if __name__ == '__main__':
    # ←, ↖, ↑, ↗, →, ↘, ↓, ↙
    move_dirs = ((0, -1), (-1, -1), (-1, 0), (-1, 1),  (0, 1), (1, 1), (1, 0), (1, -1))
    # ↖, ↗, ↘, ↙
    search_dirs = [(-1, -1), (-1, 1), (1, 1), (1, -1)]

    N, M = map(int, stdin.readline().split())
    board = [list(map(int, stdin.readline().split())) for _ in range(N)]
    cloud_loc = ((N - 1, 0), (N - 1, 1), (N - 2, 0), (N - 2, 1))

    for _ in range(M):
        d, s = map(int, stdin.readline().split())
        simulation(d - 1, s)