마법사 상어와 블리자드 [삼성 기출]

1. 문제 접근 방법

- 구현 문제이다. 단, 처음에 입력된 board를 배열에 옮겨 담으면,

  그 이후에는 board를 신경쓰지 않고, 배열로만 문제를 풀이할 수 있다. 

-> 이 문제 같은 경우는 구슬이 다 폭발되었을 때, 엣지 케이스를 잘 고려하는 것이 중요하다.

-> 항상 여러 엣지 케이스에 대해 잘 고려하고, 그것을 제출 전에 미리 테스트해보는 습관을 가져야겠다. 

 

2. 코드

import copy 

N, M = map(int, input().split())

board = [] 

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

for i in range(N):
    row = list(map(int, input().split()))
    board.append(row)

arr = [] 
arr.append(-1)
magics = []

point = 0 

for i in range(M):
    d, s = map(int, input().split())
    magics.append([d, s])


sx = N // 2 
sy = N // 2 

time = 0

## board를 전체를 순회하면서, 1,2,3 구슬을 
## arr 배열에 담아준다. 이 때, 0이 등장하면, 더 이상 구슬이 없다는 뜻이므로,
## 반복문을 탈출한다. 
for i in range(2*N-1):
    
    d = i % 4
    
    if d == 0 or d == 2:
        time += 1 
    
    reachEnd = False    
    
    for j in range(time):
        nx = sx + dx[d]
        ny = sy + dy[d]
        
        if ny < 0 or board[nx][ny] == 0:
            reachEnd = True
            break
        
        arr.append(board[nx][ny])
        sx = nx
        sy = ny 
        
    
    if reachEnd == True:
        break 
        
        
## 구슬을 폭발시킨다
## 이 때, arr 배열을 뒤에서부터 순차적으로 탐색하면서,
## 4개 이상 연속으로 같은 구슬이 등장하면, 
## 그 구슬들을 제거하고, point를 계산해서 넣어준다. 
## 폭발은 반복적으로 진행하되, 더 이상 폭발 카운트가 없으면 
## while문을 탈출한다. 
def explodeMarbles():
    
    global point 
    
    
    while True:
        
        explodeCnt = 0 
    
        arrLen = len(arr)
        curr = arr[arrLen-1]
        cnt = 1
    
    
        for i in range(arrLen-2, -1, -1):
        
            if curr == arr[i]:
                cnt += 1 
            else:
                if cnt >= 4:
                    explodeCnt += 1 
                    point += cnt*curr 
                    for j in range(i+cnt, i, -1):
                        arr.pop(j)
                    
                curr = arr[i]
                cnt = 1 
            
    
    
        
        if explodeCnt == 0:
            break 
        
    
    
    
    
## 구슬 정보를 업데이트한다
## 단, 이 때 주의하여야 할 점은 
## 구슬의 폭발로 인해 가운데 상어만 제외하고, 
## 아무런 구슬이 남아 있지 않은 상황을 고려하여야 한다는 점이다.
## 이와 같이 예외 케이스 혹은 엣지 케이스를 고려하는 것은 구현 문제에서 매우 중요하다. 
## 새로운 배열 newArr에 cnt와 curr을 차례대로 넣어준다. 
## 그리고, 전체 board의 크기를 뛰어넘지 않도록 고려하는 것도 필요하다. 
## 그 다음, 새로운 newArr을 원래 배열 arr에 덮어쓴다. 
def updateMarbles(): 
    
    global arr 
    
    if len(arr) == 1:
        return 
    
    newArr = [] 
    newArr.append(-1)
    
    curr = arr[1]
    cnt = 1 
    
    for i in range(2, len(arr)):
        
        if curr == arr[i]:
            cnt += 1 
        else:
            
            newArr.append(cnt)
            newArr.append(curr)
            
            curr = arr[i]
            cnt = 1 
            
            
    newArr.append(cnt)
    newArr.append(curr)
    if len(newArr) > N*N:
        newArr = newArr[0:N*N]
    
    
    arr = copy.deepcopy(newArr)
        
    
    
    
    
    
    
    
## dIdx에 담아 놓은 인덱스들을 따라서,
## 가장 큰 인덱스부터 순차적으로 하나씩 줄여가면서
## arr 배열에서 제거해준다. 
def breakMarbles(dIdx):
    
    dLen = len(dIdx)
    
    for i in range(dLen-1, -1, -1):
        if dIdx[i] <= len(arr)-1:
            arr.pop(dIdx[i])
        
        



## magics에 있는 d,s에 대해서 각각 순회한다
for d, s in magics:
    
    curr = 0
    gap = 0 
    
    dIdx = [] 
    
    ## d가 각각 1,2,3,4일 때, 
    ## 배열에서의 시작점을 고른다. 
    if d == 1:
        curr = 7
        gap = 7 
    elif d == 2:
        curr = 3
        gap = 3
    elif d == 3:
        curr = 1
        gap = 1 
    elif d == 4:
        curr = 5
        gap = 5 
        
    ## 제거할 인덱스들을 모아 놓은 배열 dIdx를 만들고,
    ## curr을 추가한다. 
    dIdx.append(curr)
    
    ## 제거할 인덱스들을 전부 배열 dIdx에 추가한다. 
    for i in range(s-1):
        gap += 8
        curr += gap
        dIdx.append(curr)
        
    ## 구슬을 파괴한다. 이 때, 파괴할 인덱스들은 dIdx에 담아 놓았다.     
    breakMarbles(dIdx)
    
    explodeMarbles()


    updateMarbles() 




## 최종적으로 점수를 출력한다. 
print(point)