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

문제 이동

소요시간 : 2시간 30분
체감 난이도 : 중하
유형 : 구현, 그래프

어려웠던 것

• 2차원 배열을 1차원 배열로 바꾸는 dictionary와 list를 만들 때 for문을 너무 많이 돌리나 싶어 while문으로 변수에 변화를 주며 돌렸다.

• 문제는 어렵지 않았으나 마지막에 구슬 그룹화할 때 cnt를 1부터 시작했어야 했는데 0부터 시작해서 그거 찾느라 시간을 많이 낭비했다.

• 다른 사람이 블로그에 올려놓은 코드를 참고하며 풀었다.

  참고 블로그 : https://kimjingo.tistory.com/171

  감사합니다
  

코드

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move_lst = [tuple(map(int, input().split())) for _ in range(M)]


dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

board2order = {}
order2ball = [-1] * N**2
order2ball[0] = 0
# 좌표 -> 번호
def gen_order_lst(r,c):
    global board2order, order2ball

    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)] # 좌 하 우 상
    step = 1
    d = 0
    cnt = 1
    while True:
        for _ in range(step):
            r += directions[d][0]
            c += directions[d][1]
            if cnt >= N**2:
                break
            board2order[(r, c)] = cnt
            order2ball[cnt] = board[r][c]
            cnt += 1
        d = (d + 1) % 4
        if d % 2 == 0:
            step += 1

        if cnt == N**2:
            break

# 파괴
def destroy(d, s):
    for i in range(1, s+1):
        order = board2order[(N//2 + dir[d-1][0] * i, N//2 + dir[d-1][1] * i)]
        order2ball[order] = -1

# 재정렬
def arrangement():
    global order2ball
    del_cnt = order2ball.count(-1)
    order2ball = [ball for ball in order2ball if ball != -1]
    order2ball.extend([0] * del_cnt)

# 폭발
def bomb():
    global order2ball, flag, result
    now = order2ball[1]
    cnt = 1
    for i in range(2, N**2 - 3):
        if now == order2ball[i]:
            cnt += 1
        else:
            if cnt >= 4 and now > 0:
                result[now] += cnt
                for j in range(1, cnt+1):
                    order2ball[i-j] = -1
                    flag = True
            cnt = 1
            now = order2ball[i]

# 연속 그룹
def group():
    result = [0]
    now = order2ball[1]
    cnt = 1
    for i in range(2, N**2 - 3):
        if now == order2ball[i]:
            cnt += 1
        else:
            result.extend([cnt, now])
            cnt = 1
            now = order2ball[i]

    return result

result = {1: 0, 2: 0, 3: 0}
r, c = N//2, N//2
# 1차원 배열 생성
gen_order_lst(r,c)
# print("1차원 배열 : ", order2ball)
# m번 시전
for d, s in move_lst:
    # 파괴
    destroy(d, s)
    # print("파괴 후", order2ball, len(order2ball))
    # 재정렬
    arrangement()
    # print("재정렬 후", order2ball, len(order2ball))
    # 4개 연속 없을 때까지 터뜨리고 재정렬
    while True:
        flag = False
        bomb()
        # print("폭발 후", order2ball, len(order2ball))
        if flag:
            arrangement()
            # print("재정렬 후", order2ball, len(order2ball))
        else:
            # print("폭발 끝")
            break
    # 구슬 변화
    order2ball = group()
    if len(order2ball) > N**2:
        order2ball = order2ball[:N**2]
    elif len(order2ball) < N**2:
        order2ball.extend([0] * (N**2 - len(order2ball)))
    # print("구슬 변화 후", order2ball)

# print(result)
print(result[1] + 2 * result[2] + 3 * result[3])