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

문제

21611번: 마법사 상어와 블리자드 (acmicpc.net)

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

풀이

풀이에 상당한 시간이 소요된 문제이다.

본 문제에서의 핵심은, 블리자드 마법을 시전할 때외에는 전부 블리자드의 진행방향으로만 보드를 탐색한다는 것이다. 즉 마법 시전 이후엔 매번 보드를 블리자드 진행방향으로 탐색하기 보다는 일차원 리스트로 해석해서 구현하는것이 훨씬 편하다는 점을 눈치채야한다.

블리자드 진행방향에 있는 요소들을 일차원 리스트에 담을때는, 이전 문제들과 마찬가지로 보드 경계를 주의하도록 한다. 또한 보드위에 구슬이 항상 존재해야한다는 조건이 없으므로, 보드에 구슬이 없을 때 역시 주의하도록 한다.

블리자드 시전 이후의 요구 사항들은 일차원 리스트 내의 연속된 요소들의 값을 비교하는 것이 주된 목표이다. 즉 리스트 내에 두 개 이상의 요소들이 존재한다는것이 전제되어 있으므로, 인덱스 에러를 주의해서 구현하도록 한다.

 

구현 로직 자체는 맞았으나, 보드 경계와 구슬이 없는 경우를 생각하지 못하여 많은 시간이 소요되었다. 실전에서는 모든 구슬이 같은 경우, 보드가 꽉 차 있는 경우, 구슬이 없는 경우 등 여러 케이스들을 생각해서 코드를 돌려봐야겠다.

# N,S,W,E
dRow = [0,-1,1,0,0]
dCol = [0,0,0,-1,1]

N,M = map(int,input().split())
board =[[0]*(N+1)]
for _ in range(N):
    board.append([0] + list(map(int,input().split())))
cr,cc = (N+1)//2,(N+1)//2

# 블리자드 생성
bliz = [[[0, 0] for col in range(N + 1)] for row in range(N + 1)]
visited = [[0]*(N+1) for _ in range(N+1)]
br,bc = 1,1
dir = [0,1]
while True:
    visited[br][bc] = 1
    bliz[br][bc] = tuple(map(lambda x : -x, dir))
    nbr,nbc = br+dir[0],bc+dir[1]
    if not (1 <= nbr <= N and 1 <= nbc <= N and visited[nbr][nbc] == 0):
        dir = [dir[1],-dir[0]]
        nbr,nbc = br+dir[0],bc+dir[1]
    if br == cr and bc == cc:
        break
    br,bc = nbr,nbc

# 1,2,3
explosion = [0,0,0,0]

for _ in range(M):
    d,s = map(int, input().split())
    # 블리자드 시전
    for _s in range(1,s+1):
        nRow,nCol = cr+dRow[d]*_s,cc+dCol[d]*_s
        board[nRow][nCol] = 0
    # 구슬 밀기
    marbles = []
    x, y = cr, cc
    while 1 <= x <= N and 1 <= y <= N:
        if board[x][y] > 0:
            marbles.append(board[x][y])
            board[x][y] = 0
        dx, dy = bliz[x][y]
        nx, ny = x+dx,y+dy
        if not (1 <= nx <= N and 1 <= ny <= N):
            break
        x,y = nx,ny
    if not marbles:
        break
    # 구슬 num,cnt 로 묶기
    new_marbles = [[marbles[0], 1]]
    for i in range(1,len(marbles)):
        if marbles[i] == new_marbles[-1][0]:
            new_marbles[-1][1] += 1
        else:
            new_marbles.append([marbles[i], 1])

    while True:
        # 구슬 4개 이상 연속 터뜨리기
        temp = []
        for num,cnt in new_marbles:
            if cnt < 4:
                temp.append([num,cnt])
            else:
                explosion[num] += cnt
        # 구슬 갱신
        if not temp:
            break
        elif len(temp) == 1:
            new_marbles = [[*temp[0]]]
            break
        _temp = [[*temp[0]]]
        for i in range(1,len(temp)):
            if temp[i][0] != _temp[-1][0]:
                _temp.append([*temp[i]])
            else:
                _temp[-1][1] += temp[i][1]
        new_marbles = [[*elem] for elem in _temp]
        # 검사
        for num,cnt in _temp:
            if cnt >= 4:
                break
        else:
            break
    # 그룹으로 재배치
    x,y = cr,cc-1
    for num,cnt in new_marbles:
        dx,dy = bliz[x][y]
        board[x][y] = cnt
        x += dx
        y += dy
        if not (1 <= x <= N and 1 <= y <= N):
            break
        dx,dy = bliz[x][y]
        board[x][y] = num
        x += dx
        y += dy
        if not (1 <= x <= N and 1 <= y <= N):
            break

answer = 0
for i,v in enumerate(explosion):
    answer += i*v
print(answer)