백준 GOLD 1 [21611번] 마법사 상어와 블리자드 {언어 : Python}

문제 링크

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

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

정답 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
blizzard = [list(map(int, input().split())) for _ in range(N)]
useMagics = [list(map(int, input().split())) for _ in range(M)]

# 처음부터 가공해서 넣기
# 달팽이 시작
sr = sc = N//2
newBlizzard = [blizzard[sr][sc]]
# 좌 하 우 상
directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d = 3
# 1 1 2 2 3 3 4 4 5 5 ... N-1
ways = []
cnts = [0]
cnt = 0
for num in range(1, N):
    ways.append(num)
    ways.append(num)
    for _ in range(num * 2):
        cnt += 1
        cnts.append(cnt)
ways.append(N-1)
for _ in range(N-1):
    cnt += 1
    cnts.append(cnt)

for w in ways:
    d = (d + 1) % 4
    for _ in range(w):
        sr += directions[d][0]
        sc += directions[d][1]
        newBlizzard.append(blizzard[sr][sc])

# 상1 하2 좌3 우4
useBlizzardLocations = {
    3: [0, 1], # 1 9 17 25 33
    2: [0, 3], # 3 11 19 27
    4: [0, 5],
    1: [0, 7]
}

for i in range(1, 5):
    for j in range(N//2-1):
        useBlizzardLocations[i].append(useBlizzardLocations[i][-1] * 2 - useBlizzardLocations[i][-2] + 8)

def compression():
    tmpIdx = 1
    for jdx in range(1, N ** 2):
        if newBlizzard[jdx]:
            newBlizzard[tmpIdx], newBlizzard[jdx] = newBlizzard[jdx], newBlizzard[tmpIdx]
            tmpIdx += 1
    return

score = 0
def delete(removeList, checkList):
    global score
    for idx in range(len(checkList)):
        score += checkList[idx] * len(removeList[idx])
    for lst in removeList:
        for l in lst:
            newBlizzard[l] = 0
    return

# 지우기
for di, si in useMagics:
    for idx in range(1, si+1):
        newBlizzard[useBlizzardLocations[di][idx]] = 0
    # 땡기기
    compression()

    # 폭발시키기
    while True:
        removeList = []
        checkList = []
        tmpList = []
        tmp = -1
        for idx in range(1, N**2):
            nbi = newBlizzard[idx]
            if nbi:
                if nbi == tmp:
                    tmpList.append(idx)
            if nbi != tmp:
                if len(tmpList) >= 4:
                    removeList.append(tmpList)
                    checkList.append(tmp)
                tmpList = [idx]
                tmp = nbi
            if idx == N ** 2 - 1 and len(tmpList) >= 4:
                removeList.append(tmpList)
                checkList.append(nbi)

        if not removeList:
            break
        delete(removeList, checkList)
        compression()

    # 뿔리기
    changeBlizzard = [0]
    prev = newBlizzard[1]
    newList = [prev]
    for kdx in range(2, N**2):
        currentNumber = newBlizzard[kdx]
        if prev == currentNumber:
            newList.append(prev)
        else:
            changeBlizzard.append(len(newList))
            changeBlizzard.append(prev)
            if currentNumber == 0:
                break
            else:
                prev = currentNumber
                newList = [prev]
    lenChangeBlizzard = len(changeBlizzard)
    if lenChangeBlizzard > N ** 2:
        newBlizzard = changeBlizzard[:N**2]
    else:
        for _ in range(N**2 - lenChangeBlizzard):
            changeBlizzard.append(0)
        newBlizzard = changeBlizzard

print(score)

풀이 방법

1. 우선 이차원 배열을 일차원으로 바꾼다.
   1. 2차원 배열로 하는 방법도 틀린 것은 아니지만 순서라는 것이 정해진 달팽이 배열이다보니 일차원으로 푸는 것이 더 쉬워보였다.
   2. 0인 상어를 시작으로 N ** 2 - 1번 인덱스까지 append해서 새로 만들어준다.
2. 상하좌우에 해당하는 딕셔너리를 만든다.
   1. 이차원 배열이 사라졌으므로 몇 번째 인덱스를 지워야 할지 추적해야 하기 때문에 미리 만들었다.
3. 마법을 사용한다.
   1. 방향과 거리에 따라서 미리 만들어둔 딕셔너리를 이용해서 지운다.
      1. 지운 배열을 압축한다.
         1. 압축한 배열에서 길이가 4이상인 그룹을 찾는다.
         2. 폭발시킨다.
            1. 폭파 시키는 과정에서 구슬의 번호 * 구슬의 개수 만큼 score에 더해준다.
         3. 다시 압축한다.
      2. 반복 과정에서 폭발 시킬 그룹이 없으면 빠져나온다.
   2. 새로 blizzard 배열을 만든다.
      1. 각 그룹의 개수, 해당 그룹의 구슬의 번호를 순서대로 append 해준다.
      2. 새로 만든 배열이 N ** 2을 초과할 경우 구슬을 채울 필요가 없기 때문에 슬라이싱 해준다.
      3. 길이가 작을 경우 0을 채워주고 슬라이싱 한다.
4. 마법 사용이 끝나면 score를 출력한다. 

느낀점

• 시뮬레이션 문제는 가장 중요한게 문해력인 것 같다.
• 어려운 알고리즘을 사용하는 것은 아니며 조금 노가다라고 느껴지는 문제다.
• 한 번 제출에 통과할 줄은 몰랐다.