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

 

---

 

문제

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

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

 

풀이

python3으로는 시간초과가 나서 pypy3으로 제출했다.

 

 

우선 구름의 위치를 저장하는 배열을 선언하고, 각 구름의 이동을 수행한다.

 

배열의 범위를 초과하면 순환되는 구조이기에 그 부분부터 구현하면 된다. '마법사 상어와 파이어볼' 에서 처리한것과 똑같이 처리해주면 된다. (아래 참고)

---

1. 파이어 볼 이동
   • 2차원 배열을 돌면서 한개라도 파이어볼이 있다면 현재위치 + 방향 * 속도 만큼 이동해주면 된다.
   • 단 해당 문제는 배열의 범위를 벗어나면 반대쪽에서 나타난다.
   • 만약 n이 5인데 0 의 위치에서 5만큼 이동해야할 경우, 한바퀴를 빙 돌아 제자리에 오는것이다. 
   • 식으로 나타내면  '현재위치%n' 으로 표현할 수 있다. 양수같은 경우에는 모두 처리 가능하다.
   • 음수일때는 ' n - ((-현재위치)%n) ' 으로 계산하면 원하는 값을 얻을 수 있다.
     • 단, '-현재위치%n' 이 0이 나오게 된다면 n-0 = n 으로, 범위를 벗어나게 된다. (배열은 0 ~ 4 니까)
       따라서 이 때만 0으로 예외처리를 해주면 된다. (한바퀴 빙 도는거임)

---

결과배열을 하나 선언하고, 위의 규칙에 따라서 이동된 좌표값들을 저장해준다.

 

결과배열을 순환하면서 물의 양을 1 증가시켜준다.

 

결과배열을 순회하면서 대각선을 검사하면서 물바구니가 있다면 물의양을 증가시켜준다.

 

2차원 물 배열을 순회하면서, 해당좌표가 결과배열에 없고, 2이상의 물을 가지고 있으면 임시배열에 좌표들을 저장해준다. 그리고 다 추가해줬으면 기존배열에 복사해주면 된다.

 

해당 과정을 m번 반복하면 끝!

 

 

코드

import copy
from sys import stdin

def changePosition(x, y):

    if x < 0:
        x = n - ((-x)%n)
        if x == n: x = 0
    if y < 0:
        y = n - ((-y) % n)
        if y == n: y = 0
    return x % n, y % n


def moveCloud(cloud, direct, speed):
    tempCloud = []
    for val in cloud:

        nx = val[0] + dx[direct] * speed
        ny = val[1] + dy[direct] * speed
        tempCloud.append(changePosition(nx, ny))

    return tempCloud


dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
dia = [1, 3, 5, 7]
n, m = map(int, input().split())
board = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
# 구름의 위치를 저장한 배열
cloud = [(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)]
command = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(m) ]
for d, s in command:
    d -= 1
    # 이동한다.
    resultCloud = moveCloud(cloud, d, s)

    # 물의 양을 증가시켜준다.
    for val in resultCloud:
        board[val[0]][val[1]] += 1

    # 대각선 검사한다.
    for val in resultCloud:
        for i in range(4):
            nx = val[0] + dx[dia[i]]
            ny = val[1] + dy[dia[i]]

            # 대각선에 바구니가 있다면 값을 증가시켜준다.
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 0:
               board[val[0]][val[1]] += 1

    # 원래 구름있던 위치말고 2이상인곳에 구름이 새로 생기고, 2만큼 감소해준다.
    tempCloud = []
    for i in range(n):
        for j in range(n):
            if (i, j) not in resultCloud:
                if board[i][j] >= 2:
                    tempCloud.append((i, j))
                    board[i][j] -= 2
    cloud = copy.deepcopy(tempCloud)

answer = 0
for i in range(n):
    for j in range(n):
        answer += board[i][j]
print(answer)

 

후기

 

문제만 봤을때는 좀 귀찮을 거 같았는데, 구현은 굉장히 금방한편이었다. 좌표벗어날때 재정의하는 테크닉을 요전에 해서 그런듯