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

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

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

 

# 21611 마법사 상어와 블리자드

# 빙글빙글 돌면서 보는 숫자들을 모아 하나의 리스트로 만들어주는 함수
def make_one():
    cur_r = N // 2
    cur_c = N // 2
    cur_dir = 0
    num = 1
    while cur_c >= 0:
        for _ in range(num):
            cur_r += dr[cur_dir]
            cur_c += dc[cur_dir]
            # 범위 밖이면 백트래킹
            if cur_c == -1:
                return
            if grounds[cur_r][cur_c] > 0:
                one_list.append(grounds[cur_r][cur_c])
            # 0이면 백트래킹
            elif grounds[cur_r][cur_c] == 0:
                return
        if cur_dir % 2 == 1:
            num += 1

        cur_dir = (cur_dir + 1) % 4

    return


# 일렬로 나열, 4개 이상 연속하면 폭파시키기
def boom():
    temp_list = one_list[:]
    check_again = True
    pop_index = list()
    while check_again:
        check_again = False
        result_list = list()
        num = 1
        if temp_list:
            prev_num = temp_list[0]
            
            for i in range(1, len(temp_list)):
                if prev_num == temp_list[i]:
                    num += 1
                else:
                    result_list.append([num, prev_num])
                    prev_num = temp_list[i]
                    num = 1
            # 마지막은 수동으로 넣기
            result_list.append([num, prev_num])

            # temp_list 다시 만들기
            temp_list = list()
            for num, prev_num in result_list:
                if num >= 4:
                    result[prev_num] += num
                    check_again = True
                else:
                    temp_list.extend([prev_num] * num)

    return temp_list


def make_group():
    # 갯수 세어서 하나의 그룹으로 만들기
    result_list = list()
    num = 1
    if one_list:
        prev_num = one_list[0]

        for i in range(1, len(one_list)):
            if prev_num == one_list[i]:
                num += 1
            else:
                # 지금까지 쌓은 갯수 넣기
                result_list.extend([num, prev_num])
                prev_num = one_list[i]
                num = 1

        # 마지막은 수동으로 넣기
        result_list.extend([num, prev_num])

    return result_list[:N ** 2]


# 좌 하 우 상
dr = [0, 1, 0, -1]
dc = [-1, 0, 1, 0]

# 0 상 하 좌 우
ddr = [0, -1, 1, 0, 0]
ddc = [0, 0, 0, -1, 1]

N, M = map(int, input().split())
grounds = [list(map(int, input().split())) for _ in range(N)]
result = [0, 0, 0, 0]
ds = list()
for _ in range(M):
    di, si = map(int, input().split())
    ds.append([di, si])

for idx in range(M):
    di, si = ds[idx]
    temp_r = N // 2
    temp_c = N // 2
    # 구슬 파괴
    for _ in range(si):
        temp_r += ddr[di]
        temp_c += ddc[di]
        if 0 <= temp_r < N and 0 <= temp_c < N:
            grounds[temp_r][temp_c] = -1

    # 순서대로 체크하기, 일렬로 만들기
    one_list = list()
    make_one()

    # 4개 이상 연속하는 구슬 폭파
    one_list = boom()

    # 하나의 그룹으로 만들기
    one_list = make_group()

    # 칸에 순서대로 넣기
    cur_r = N // 2
    cur_c = N // 2
    cur_dir = 0
    num = 1
    idx = 0
    grounds = [[0] * N for _ in range(N)]
    while cur_c >= 0:
        for _ in range(num):
            cur_r += dr[cur_dir]
            cur_c += dc[cur_dir]
            if cur_c == -1:
                break
            if idx < len(one_list):
                grounds[cur_r][cur_c] = one_list[idx]
            else:
                cur_c = -1
                break
            idx += 1
        if cur_dir % 2 == 1:
            num += 1

        cur_dir = (cur_dir + 1) % 4

ans = 0
for i in range(1, 4):
    ans += result[i] * i
print(ans)

"""
제출하자마자 틀렸습니다
거의 마지막 부분 칸에 순서대로 넣을 때 다음을 추가
if cur_c == -1:
    break

44% 틀렸습니다.
문제 조건대로 풀기,,
4개 이상 폭파시킬 때 
폭파시키고 나서 임의로 첫 번째 idx부터 다시 탐색함
시키는대로 4개 이상 이어지는 부분 다 찾고나서 터뜨린 뒤에
다시 처음부터 탐색해야 한다.
"""

 

 

 

예전 풀이

 

# 21611 마법사 상어와 블리자드

# 하 우 상 좌
dr = (0, 1, 0, -1, 0)
dc = (0, 0, 1, 0, -1)

# 0, 상, 하, 좌, 우
bli_rc = [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)]



# 일렬 리스트 만들기
def make_one_list():
    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]
                one_list.append(blocks[current_r][current_c])
        move_num += 2

        if blocks[current_r][current_c + dc[i]] == 0:
            break
    return


# blizrd 마법 이후 블록 재배치
def make_blocks():
    for i in range(N + 1):
        for j in range(N + 1):
            blocks[i][j] = 0

    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    one_list_idx = 0
    length = len(one_list)
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]
                if length <= one_list_idx:
                    return
                while one_list[one_list_idx] == 0:
                    one_list_idx += 1
                    if length <= one_list_idx:
                        return
                blocks[current_r][current_c] = one_list[one_list_idx]
                one_list_idx += 1 
        move_num += 2
    return


# 4개 연속이면 터뜨리기
def pop_one_list():
    global one_list
    new_one_list = list()
    bomb_check = 0
    cnt = 1
    temp = -1
    for i in range(len(one_list)):
        if one_list[i] != temp:
            temp = one_list[i]
            if cnt >= 4:
                bomb_check = 1
                bomb_num[new_one_list[-1]] += cnt
                for _ in range(cnt):
                    new_one_list.pop()
            cnt = 0
        new_one_list.append(one_list[i])
        cnt += 1
    if cnt >= 4:
        bomb_check = 1
        bomb_num[new_one_list[-1]] += cnt
        for _ in range(cnt):
            new_one_list.pop()
    one_list = new_one_list[:]
    return bomb_check


# 구슬 변화(갯수, 번호)
def evolution():
    global blocks
    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    cnt = 0
    bf_num = blocks[current_r][current_c - 1]
    flag = 0
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]

                if current_c <= 0 or current_r > N or blocks[current_r][current_c] == 0:
                    flag = 1
                    break

                # 전후 숫자가 달라지면 visited 초기화 가능
                if blocks[current_r][current_c] == bf_num:
                    cnt += 1
                elif blocks[current_r][current_c] != 0:
                    evo_list.append(cnt)
                    evo_list.append(bf_num)
                    cnt = 1
                    bf_num = blocks[current_r][current_c]
                else:
                    break
            if flag == 1:
                break
        if flag == 1:
            break
        move_num += 2


    evo_list.append(cnt)
    evo_list.append(bf_num)
    

    # 블록 재배치
    new_blocks = [[0] * (N + 1) for _ in range(N + 1)]

    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    move_num = 2
    evo_list_idx = 0
    length = len(evo_list)
    while current_c > 0:
        for i in range(1, 5):
            for j in range(move_num):
                # 처음엔 왼쪽으로 이동
                if i == 1 and j == 0:
                    current_c -= 1
                else:
                    current_r += dr[i]
                    current_c += dc[i]
                if length <= evo_list_idx:
                    break
                if current_r <= 0 or current_c <= 0:
                    blocks = new_blocks[:]
                    return
                new_blocks[current_r][current_c] = evo_list[evo_list_idx]
                evo_list_idx += 1
        move_num += 2
    blocks = new_blocks[:]
    return


N, M = map(int, input().split())
blocks = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
one_list = list()
move_list = list()
bomb_num = [0, 0, 0, 0]
for _ in range(M):
    temp_r, temp_c = map(int, input().split())
    move_list.append([temp_r, temp_c])

for blizard_d, blizard_s in move_list:
    # blizard 마법
    current_r = (N // 2) + 1
    current_c = (N // 2) + 1
    for _ in range(blizard_s):
        current_r += bli_rc[blizard_d][0]
        current_c += bli_rc[blizard_d][1]
        blocks[current_r][current_c] = 0

    one_list = list()
    # blizard 마법 이후 일렬 리스트로 붙이기
    make_one_list()

    # blizard 마법 이후 블록 재배치
    make_blocks()

    one_list = list()
    # 일렬 리스트 만들기
    make_one_list()

    again = 1
    while again:
        # 4개 연속이면 터뜨리기
        again = pop_one_list()

    # 블록 재배치
    make_blocks()

    evo_list = list()
    # 구슬 변화(갯수, 번호)
    evolution()

ans = 0
for i in range(1, 4):
    ans += bomb_num[i] * i

print(ans)