백준 21611번 : 마법사 상어와 블리자드

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

21611번: 마법사 상어와 블리자드

 

 

복잡한 구현문제이다.

 

전체적인 구조는 1시간정도 걸려서 구현했는데, 구슬폭파 부분에서 시간이 많이 걸렸다.

차례대로 구슬 폭파를 하지 않고, 한꺼번에 해야하는데 차례대로 구슬폭파를 하는 식으로 구현해서 몇 시간이나 낭비했다.

 

아이디어

먼저 N*N 크기의 맵의 각 자리에 숫자를 부여한 뒤, 이를 참고해서 1번 자리에 있는 숫자부터 N*N-1번 자리에 있는 숫자까지 maps 배열에 넣어준다.

그리고 구슬을 공격할 때는, 맵의 자리 숫자를 참고하여 maps배열의 몇 번째 원소를 지우면 되는지 정한다.

구슬을 터트릴때는 메모이제이션을 활용하여 remove_list에 해당 자리와 동일한 숫자가 해당 자리까지 몇 개나 연속되는지 확인 후, 숫자가 바뀔 때, 4개 이상인지 확인하여 지워버린다. 이 때, map과 remove_list에서 동일한 부분을 지운다.

remove_list를 참고하여 새로운 map을 만들어준다. 숫자가 바뀔 때, 어떤 숫자가 몇 개 연속되어있는지 remove_list를 통해 알 수 있다.

함수 설명

1. mapsWithNumbers : 다음 그림과 같이 N*N 크기의 맵의 각 자리에 숫자를 부여한다

 

2. attackMap : d와 s를 파라미터로 받아서 구슬 공격

 

3. removeMap : 4개이상 연속한 구슬을 터트린다. 이 때 remove_list를 리턴함

 

4. makeNewMap : remove_list를 통해 새로운 맵을 만든다.

 

import sys
input = sys.stdin.readline

attacks = []
attack_direction = [(-1,0), (1,0), (0,-1), (0,1)]
answer = [0,0,0]

n,m = map(int, input().rstrip().split())

maps = [0] * (n*n)
shark_x, shark_y = (n+1)//2 - 1, (n+1)//2 - 1

inputs = []
for _ in range(n):
    inputs.append(list(map(int,input().rstrip().split())))

for _ in range(m):
    attacks.append(list(map(int,input().rstrip().split())))

def mapsWithNumbers(n):
    number_maps = [[0 for _ in range(n)] for _ in range(n)]
    direction = 0
    start_x = -1
    start_y = 0
    now_number = n*n-1
    now_length = n

    while now_number>0:
        if direction == 0:
            for _ in range(now_length):
                start_x += 1
                number_maps[start_y][start_x] = now_number
                now_number -= 1

        elif direction == 1:
            now_length -= 1
            for _ in range(now_length):
                start_y += 1
                number_maps[start_y][start_x] = now_number
                now_number -= 1

        elif direction == 2:
            for _ in range(now_length):
                start_x -= 1
                number_maps[start_y][start_x] = now_number
                now_number -= 1

        else:
            now_length -= 1
            for _ in range(now_length):
                start_y -= 1
                number_maps[start_y][start_x] = now_number
                now_number -= 1

        direction = (direction+1) % 4

    return number_maps

number_maps = mapsWithNumbers(n)

for y in range(n):
    for x in range(n):
        maps[number_maps[y][x]] = inputs[y][x]

i = 1
while i<len(maps):
    if maps[i] == 0 :
        del(maps[i])
    else:
        i += 1

def attackMap(d,s):
    my,mx = attack_direction[d-1]
    ny, nx = shark_y, shark_x

    for i in range(s):
        ny = my+ny
        nx = mx+nx

        if ny>=0 and ny<n and nx>=0 and nx<n:
            now = number_maps[ny][nx] - i

            if now < len(maps):
                del(maps[now])

def removeMap():
    bools = False
    remove_list = [0] * (n*n)
    now = maps[1]
    count = 0
    i = 1

    while i< len(maps):
        remove_list[i-1] = [now,count]
        if now != maps[i]:
            if count >=4:
                del(maps[i-count:i])
                del(remove_list[i-count:i])
                answer[now-1] += count
                i = i - count
                count = 0
                now = maps[i]
                bools = True
                #now,count = remove_list[i-1]
            else:
                count = 1
                now = maps[i]
                i += 1
        else:
            count += 1
            i += 1

    remove_list[i-1] = [now,count]

    if count >= 4:
        del(maps[-count:])
        remove_list = remove_list[0:len(maps)]
        answer[now-1] += count
    return remove_list, bools

def makeNewMap(remove_list):
    maps = [0]

    for i in range(1,len(remove_list)-1):
        if remove_list[i+1] != 0:
            if remove_list[i][0] != remove_list[i+1][0]:
                maps.append(remove_list[i][1])
                maps.append(remove_list[i][0])
        elif remove_list[i] != 0:
            maps.append(remove_list[i][1])
            maps.append(remove_list[i][0])
            break
            
        if len(maps) >= n*n:
            maps = maps[0:n*n]
            return maps

    if len(maps) >= n*n:
        maps = maps[0:n*n]
    return maps

for d,s in attacks:
    if len(maps) < 2:
        break
    attackMap(d,s)
    bools = True
    while bools:
        remove_list,bools = removeMap()
    maps = makeNewMap(remove_list)

result = answer[0] + 2*answer[1] + 3*answer[2]

print(result)