백준 20056 : 마법사 상어와 파이어볼

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

20056번: 마법사 상어와 파이어볼

1. 파이어볼의 이동 방식

 이번 문제의 특징은 파이어볼이 이동하는 방식에 있다. 벽을 넘어서면 사라지는 것이 아니라, 반대편 격자로 다시 등장하게 된다. N X N 격자가 무한히 펼쳐져 있다고 상상해보자.

 위와 같이 가운데 메인 격자를 중심으로 확장시켜서 생각할 수 있다. 인덱스 관계를 확인하기 위해 1차원 배열로 생각해보면,

위와 같이 생각할 수 있다. 첫째 줄은 메인 격자판을 기준으로(민트색 구간) 좌우로 뻗어나갔을 때 계산될 인덱스의 수이다.

 N보다 큰 경우 0과 N 사이의 값을 가질 때까지 N을 뺴주고, 1보다 작은 경우에는 N을 계속 더해서 0과 N사이의 값을 가지게 해 주면 원하는 크기만큼 이동하는 결과를 얻을 수 있다. 

while nx < 0 : nx += N
while nx >= N : nx -= N
while ny < 0 :  ny += N
while ny >= N : ny -= N

이를 이용해서 파이어볼의 정보를 하나씩 빼서 이동, 그 후 보드판에 정보를 입력해주면 된다.

 

2. 이동 이후 증식하는 파이어볼의 정보관리

 보드판 배열을 3차원으로 정의하고, 보드판 요소의 배열의 크기가 1인 경우(아무것도 하지 않고 파이어볼 정보 큐에 다시 넣음)와, 크기가 2 이상인 경우로 나누어서 풀면 된다. 

 이 때, 크기가 2 이상 경우에는 같은 위치에 있는 파이어볼의 방향 정보가 같은지, 다른지를 고려해야 하는데, 나는 여기에서 맨 처음의 파이어볼의 방향 정보를 2로 나눈 값으로 가지고 있는 뒤에, 나머지 파이어볼에 대해서 반복문으로 같은 나머지 값이 나오는지 조사하도록 하였다. 같은 값이 나왔다면 [0, 2, 4, 6], 다른 값이 나왔다면 즉시 빠져나오고 [1, 3, 5, 7]로 결정할 수 있도록 하였다. 해당 부분에 대한 코드는 다음과 같다.

check = dd[0] % 2
new_dd = [0, 2, 4, 6]
for k in range(1, len(dd)):
    if check != dd[k] % 2 :
        new_dd = [1, 3, 5, 7]
        break

3. 전체코드

메모리 : 130676 KB, 시간 : 512 ms, 풀이 시간 : 70 min

 ※ 4달 전에 풀었을 때는 테스트 케이스의 가장 긴 시간이 1532ms 였다. 그동안 공부하면서 실력이 늘긴 늘은 듯. 뿌듯

N, M, K = map(int, input().split())
f_info = []
for i in range(M):
    temp = list(map(int, input().split()))
    f_info.append([temp[0]-1, temp[1]-1, temp[2], temp[3], temp[4]])

board = [[[] for _ in range(N)] for _ in range(N)]

# 상, 상우, 우, 우하, 하, 하좌, 좌, 좌상
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

def move():
    while f_info :
        x, y, m, s, d = f_info[0]
        del f_info[0]
        nx = x + s * dx[d]
        ny = y + s * dy[d]
        while nx < 0 : nx += N
        while nx >= N : nx -= N
        while ny < 0 :  ny += N
        while ny >= N : ny -= N
        board[nx][ny].append([m, s, d])

def divide():
    for i in range(N):
        for j in range(N):
            if len(board[i][j]) == 1 :
                f_info.append([i, j, board[i][j][0][0], board[i][j][0][1], board[i][j][0][2]])
                board[i][j] = []
            if len(board[i][j]) > 1 :
                dm, ds, dd = 0, 0, []
                for k in range(len(board[i][j])):
                    dm += board[i][j][k][0]
                    ds += board[i][j][k][1]
                    dd.append(board[i][j][k][2])
                check = dd[0] % 2
                new_dd = [0, 2, 4, 6]
                for k in range(1, len(dd)):
                    if check != dd[k] % 2 :
                        new_dd = [1, 3, 5, 7]
                        break
                dm //= 5
                ds //= len(board[i][j])
                if dm != 0 :
                    for k in range(4):
                        f_info.append([i, j, dm, ds, new_dd[k]])
                board[i][j] = []

def solve():
    it = 0
    result = 0
    while it < K :
        move()
        divide()
        it += 1
    for i in range(len(f_info)):
        result += f_info[i][2]
    return result
print(solve())