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

01. 문제

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

✔ 삼성 SW 역량 테스트 기출문제

02. 접근 방법

💡 핵심 아이디어

1. 구름을 하나씩 이동시키며, 새로운 구름 위치를 방문 표시하고 해당 위치의 바구니의 물을 1씩 증가시킨다. → 구름이 담긴 배열 = 비가 온 바구니의 위치

2. 비가 내린 자리의 대각선에 위치한 바구니의 물의 양을 확인하고 기존 바구니에 빗물을 추가해준다..

3. 새로 구름을 생성하고 다음 마법을 시전한다.

1) 구름의 이동

• 구름이 이동하다 인덱스를 넘어가도 다시 처음 인덱스로 다시 돌아간다.
  • 하늘색이 원본 배열이라면 하얀색은 원본 배열을 넘어갔을 때의 배열 인덱스
  • 즉, (0, 4) 위치는 (0, 0)으로 변환된다.

- 인덱스의 주기를 N으로 설정하기:

    for cloud in clouds:
        cloud[0] = (cloud[0] + delta[direction-1][0] * speed + N * 50) % N
        cloud[1] = (cloud[1] + delta[direction-1][1] * speed + N * 50) % N

✔ 인덱스에 음수 값이 나오면 % N 연산 시 원하는 값이 나오지 않으므로 N의 배수를 더해줘서 양수 인덱스로 만든 후에 %N 연산으로 주기를 N으로 만든다.

✔ 최대 이동할 수 있는 칸 수: 50

📌 clouds 배열은 새롭게 이동한 구름의 위치(=비가 내린 바구니의 위치)로 갱신된다.

03. CODE

delta = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]

# 1. input 받기
N, M = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]      # 각 배열에 위치하는 바구니에 담긴 물의 양
clouds = [[N-1, 0], [N-1, 1], [N-2, 0], [N-2, 1]]               # 초기 구름 위치 모음

# 2. 마법을 M번 반복
for m in range(M):
    direction, speed = map(int, input().split())
    cloud_visited = [[0] * N for _ in range(N)]                 # 구름이 지나간 자리

    # 2-1. 구름을 하나씩 이동시키고, 구름의 방문 표시한다. 구름을 이동시킨 후 바구니에 물을 +1씩 증가시킨다.
    for cloud in clouds:
        cloud[0] = (cloud[0] + delta[direction-1][0] * speed + N * 50) % N          # 인덱스가 N을 주기로 반복되므로
        cloud[1] = (cloud[1] + delta[direction-1][1] * speed + N * 50) % N
        cloud_visited[cloud[0]][cloud[1]] = 1
        data[cloud[0]][cloud[1]] += 1

    # 2-2. 비가 내린 자리의 대각선 바구니 확인하고 비의 양 추가해주기
    for cloud in clouds:                                                # 여기서 clouds는 비가 내린 바구니 인덱스를 뜻한다.
        for d in (1, 3, 5, 7):                                          # 대각선 방향만 확인하기
            nr = cloud[0] + delta[d][0]
            nc = cloud[1] + delta[d][1]
            if 0 <= nr < N and 0 <= nc < N and data[nr][nc] > 0:        # 인덱스 에러 나지 않고, 빗물이 있다면
                data[cloud[0]][cloud[1]] += 1                           # 비가 온 바구니에 빗물 추가

    # 2-3. 새로 생긴 구름 clouds에 담고, 바구니 안의 비의 양 줄이기
    clouds = []
    for r in range(N):
        for c in range(N):
            if data[r][c] >= 2 and not cloud_visited[r][c]:
                data[r][c] -= 2
                clouds.append([r, c])

# 3. 마법이 끝나고 모든 비의 양 더해서 반환
total = 0
for row in range(N):
    total += sum(data[row])
print(total)