[백준 21611번]마법사 상어와 블리자드(파이썬)

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

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

구현할 것이 전체적으로 많은 문제입니다.

 

정리해보면 다음과 같습니다.

 

1. 마법으로 구슬 제거함

 

2. 제거한 칸 달팽이로 모으기

 

3. 같은 게 4개만큼 이어지면 폭파시킴

폭파시키고 2도 수행.

(더 이상 제거가 안될 때까지)

 

4. 달팽이돌면서 그룹화시켜보기

 

1까지는 할만합니다.

그런데 2부터가 참 난감하죠.

제거한 칸을 달팽이모양대로 모은다??

와...저걸 어떻게하지....??

 

처음에는 역달팽이

즉, 달팽이순서를 거꾸로가면서

빈칸을 보고 정렬하는 방식을 선택했습니다.

이 방식은 흠...

처음에는 그럴싸했으나

풀어보니깐 저만 헷갈렸습니다.

그리고 코드를 막상 짜보니

뭔가 동작이 제대로 안되는 느낌.

그렇게 눈물의 똥꼬쇼를 선보이다가

솔루션을 찾아보니

간단한 방식이 있었습니다.

그림으로 표현했는데요

먼저 그래프를 달팽이이동하면서

0이외의 숫자들을

차례대로 리스트에 받았습니다.

그 다음, 새로운 temp를 선언해주고

거기서 달팽이 이동을 시켜줍니다.

이때, 위에서 리스트에 받았던 숫자들을

차례대로 넣어줍니다.

그럼 0부분이 땡겨지면서

달팽이 순서대로 숫자가 정렬되는 게 완성됩니다.

 

다음 달팽이를 4개일 때 지우는 건

비교적 간단합니다.

현재 달팽이를 입력하고

리스트에 받습니다.

돌다가 다른 숫자가 나올 때

4개이상이 채워지면 0으로 만들어주고

아니라면 넘어가는 식으로 만들어줍니다.

그리고 2에서 구현한 걸 해주면 끝.

여기서 한가지 유의할 점은

숫자가 지워지지 않을떄까지 수행하므로

만약 숫자가 한번이라도 지워지면 2를 다시 수행

아니라면 그냥 break

 

그룹만드는 것은

달팽이로 이동하다가

같은 숫자로 이어진 걸 그룹화시킵니다.

그리고 다른 숫자가 나올 떄

리스트에 

(해당 숫자의 갯수,해당 숫자)

이렇게 넣어줍니다.

그리고 임시 temp를 만들어서

달팽이를 돌면서

해당 리스트의 숫자들을 넣어줍니다.

 

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

from copy import deepcopy
import sys

input = sys.stdin.readline

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

dx2 = [1, 0, -1, 0]
dy2 = [0, 1, 0, -1]


def move_beads(sx, sy):
    global a
    x, y = sx, sy - 1

    idx, cnt, move, turn = 0, 0, 1, 1
    beads = [a[x][y]] if a[x][y] != 0 else []
    while True:
        nx = x + dx2[idx]
        ny = y + dy2[idx]

        if a[nx][ny] != 0:
            beads.append(a[nx][ny])

        x, y = nx, ny

        if x == 0 and y == 0:
            break

        idx, cnt, move, turn = change_dir(idx, cnt, move, turn)

    x, y = sx, sy - 1
    idx, cnt, move, turn = 0, 0, 1, 1
    a = [[0] * n for _ in range(n)]

    if beads:
        a[x][y] = beads[0]
        for b in beads[1:]:
            nx = x + dx2[idx]
            ny = y + dy2[idx]
            a[nx][ny] = b

            x, y = nx, ny
            idx, cnt, move, turn = change_dir(idx, cnt, move, turn)


def change_dir(idx, cnt, move, turn):
    cnt += 1
    if cnt == turn:
        idx = (idx + 1) % 4
        cnt = 0
        move += 1
        if move % 2 == 0:
            turn += 1
            move = 0


def del_beads(sx, sy):
    global ans1, ans2, ans3
    x, y = sx, sy - 1
    idx, cnt, move, turn, flag = 0, 0, 1, 1, 0
    q = []
    while True:
        if not q:
            q.append([x, y])
        nx = x + dx2[idx]
        ny = y + dy2[idx]

        if a[nx][ny] == a[x][y]:
            q.append([nx, ny])
            if nx == 0 and ny == 0:
                if len(q) >= 4:
                    flag = 1
                    for i j in q:
                        if a[i][j] == 1:
                            ans1 += 1
                        elif a[i][j] == 2:
                            ans2 += 1
                        elif a[i][j] == 3:
                            ans += 1
                        ans[i][j] = 0

        elif a[nx][ny] != a[x][y]:
            if len(q) >= 4:
                flag = 1
                for i, j in q:
                    if a[i][j] == 1:
                        ans1 += 1
                    elif a[i][j] == 2:
                        ans2 += 1
                    elif a[i][j] == 3:
                        ans3 += 1
                    a[i][j] = 0
            q = []

        x, y = nx, ny

        if (x == 0 and y == 0) or a[x][y] == 0:
            return flag

        idx, cnt, move, turn = change(idx, cnt, move, turn)


n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
sx, sy = n // 2, n // 2

ans1, ans2, ans3 = 0, 0, 0

for _ in range(m):
    d, s = map(int, input().split())
    d -= 1

    for k in range(1, s + 1):
        nx = sx + k * dx[d]
        ny = sy + k * dy[d]

        if not 0 <= nx < n or not 0 <= ny < n:
            break

        a[nx][ny] = 0

        while True:
            move_beads(sx, sy)
            flag = del_beads(sx, sy)
            if flag == 0:
                break

        x, y = sx, sy - 1
        idx, cnt, move, turn = 0, 0, 1, 1
        flag, temp = 0, []
        while True:
            if not flag:
                beads_num, beads_cnt = a[x][y], 1
                flag = 1
            nx = x + dx2[idx]
            ny = y + dy2[idx]

            if a[nx][ny] == a[x][y]:
                beads_cnt += 1
                if nx == 0 and ny == 0:
                    temp.append(beads_cnt)
                    temp.append(beads_num)

            else:
                temp.append(beads_cnt)
                temp.append(beads_num)
                flag = 0

        x, y = sx, sy - 1
        idx, cnt, move, turn = 0, 0, 1, 1
        a = [[0] * n for _ in range(n)]

        if temp:
            a[x][y] = temp[0]
            for k in temp[1:]:
                nx = x + dx2[idx]
                ny = y + dy2[idx]
                a[nx][ny] = k

                x, y = nx, ny
                if x == 0 and y == 0:
                    break

                idx, cnt, move, turn = change_dir(idx, cnt, move, turn)

print(ans1 + 2 * ans2 + 3 * ans3)

 

솔루션을 봤더니

sx,sy-1에서 시작을 했습니다.

저는 처음에 우직하게

sx,sy에서 시작하는 식으로 구현했는데

그렇게 구현하는 것이 더 스마트했습니다.

 

https://chldkato.tistory.com/193

백준 21611 마법사 상어와 블리자드 (파이썬)

https://imksh.com/64

백준 21611 마법사 상어와 블리자드 python

https://kimjingo.tistory.com/171

[백준 21611번] 마법사 상어와 블리자드(Python 풀이)

난이도가 높은 편이므로

여러 사람들의 솔루션을 참고하면

공부하시는 데에 도움이 될 것입니다^^

 

+++++++

94퍼에서 막히던 코드를 해결하여

제가 처음에 풀었던

다소 지저분한 코드도 공개드립니다.

 

# 백준 21611번 마법사 상어와 블리자드
# 빈칸이동을 저장후 다시 쏘는 걸로 바꿔보자

from collections import deque
from copy import deepcopy

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

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

shark_x = N // 2
shark_y = N // 2

magic = []

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

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

one_bom = 0
two_bom = 0
three_bom = 0

# 달팽이 회전 어떻게 할지 넣기
snail_m = deque()
for i in range(1, N):
    snail_m.append(i)
    snail_m.append(i)

snail_m.append(N - 1)

move_d = [3, 2, 4, 1]


def boom(num):
    global one_bom
    global two_bom
    global three_bom

    if num == 1:
        one_bom += 1
    elif num == 2:
        two_bom += 1
    elif num == 3:
        three_bom += 1


def g():
    global graph
    out = 0
    tmp = 0
    m_d = 0
    now_x = shark_x
    now_y = shark_y
    group = 0
    s_x = 0
    s_y = 0
    f_x = 0
    f_y = 0
    put = deque()
    # 먼저 그룹되는 경우를 deque에 넣고
    # 다시 그려본다.
    for moving in snail_m:
        di = move_d[m_d]
        now = 0
        while now < moving:
            now_x += dx[di]
            now_y += dy[di]
            now += 1
            # 범위를 벗어나면 stop
            if now_x < 0 or now_x >= N or now_y < 0 or now_y >= N:
                out = 1
                break
            # 처음 그룹을 집어 넣는 경우
            if tmp == 0 and group == 0:
                tmp = graph[now_x][now_y]
                group += 1
            # 그룹을 계속 접어넣음-->2개를 넣을 때
            elif graph[now_x][now_y] == tmp:
                group += 1
            # 새로운 그룹을 만날 경우-->그룹 넣어주고새로 시작
            elif graph[now_x][now_y] != tmp:

                put.append(group)
                put.append(tmp)
                tmp = graph[now_x][now_y]
                group = 1

            elif graph[now_x][now_y] == 0:
                out = 1
                break

        if out == 1:
            break
        m_d = (m_d + 1) % 4

    now_x = shark_x
    now_y = shark_y
    flag = 0
    m_d = 0
    temp = [[0] * N for _ in range(N)]
    # 이제 그룹받은 걸 넣어줌
    for moving in snail_m:
        di = move_d[m_d]
        now = 0
        while now < moving:
            now_x += dx[di]
            now_y += dy[di]
            now += 1
            # print(now_x,now_y)

            if not put:
                flag = 1
                break
            tmp = put.popleft()
            temp[now_x][now_y] = tmp
        if flag == 1:
            break
        m_d = (m_d + 1) % 4
    graph = deepcopy(temp)


def snail_move_2():
    global graph
    while True:
        out = 0
        m_d = 0
        now_x = shark_x
        now_y = shark_y
        tmp = -1
        flag = 0
        now_nums = deque()
        # print(snail_m)
        for moving in snail_m:
            di = move_d[m_d]
            now = 0
            while now < moving:
                now_x += dx[di]
                now_y += dy[di]
                # print(now_x,now_y)
                # 돌아가면서, 숫자를 넣는다
                """
                if graph[now_x][now_y]==0:
                  flag=1
                  break
                """
                if len(now_nums) == 0 and tmp == -1:
                    tmp = graph[now_x][now_y]
                    now_nums.append([now_x, now_y])

                # 만약 같은 숫자를 만날 경우
                elif len(now_nums) > 0 and graph[now_x][now_y] == tmp:
                    now_nums.append([now_x, now_y])

                elif graph[now_x][now_y] != tmp and len(now_nums) > 0:
                    # 새로운 숫자를 만날 때, 그 숫자가 이전의 넣은 숫자가 아니면 판단
                    # 터트릴거냐, 아니면 냅둘거냐.

                    # 만약, 이전에 4개이상 안 받았다면 새로 시작
                    if len(now_nums) < 4:
                        tmp = graph[now_x][now_y]
                        now_nums.clear()
                        now_nums.append([now_x, now_y])
                        # print('not')
                        # print()

                    # 4개이상 받았다면, 터트려준다
                    else:
                        out = 1
                        while now_nums:
                            pop_x, pop_y = now_nums.popleft()
                            boom(graph[pop_x][pop_y])
                            graph[pop_x][pop_y] = 0
                        tmp = graph[now_x][now_y]
                        now_nums.append([now_x, now_y])

                # 끝까지 갔을 때    
                elif now_x == 0 and now_y == 0:
                    if len(now_nums) >= 4:
                        out = 1
                        while now_nums:
                            pop_x, pop_y = now_nums.popleft()
                            boom(graph[pop_x][pop_y])
                            graph[pop_x][pop_y] = 0
                        tmp = graph[now_x][now_y]
                        now_nums.append([now_x, now_y])
                now += 1
            if flag == 1:
                break
            m_d = (m_d + 1) % 4
        # 다 터트리고 달팽이 정렬
        # 터트린 게 없다면 끝내고
        # 터트린게 있다면 반복
        if out == 0:
            break
        if out == 1:
            snail_move()


def snail_move():
    global graph
    # 회오리 방향대로 이동하되, 빈칸 이외에 각 숫자를 저장한다.
    now_x = shark_x
    now_y = shark_y
    m_d = 0
    nums = []
    for moving in snail_m:
        di = move_d[m_d]
        now = 0
        while now < moving:
            now_x += dx[di]
            now_y += dy[di]
            now += 1

            if graph[now_x][now_y] != 0:
                nums.append(graph[now_x][now_y])
        m_d = (m_d + 1) % 4

    temp = [[0] * N for _ in range(N)]
    put_x = shark_x
    put_y = shark_y
    m_d = 0
    flag = 0
    for moving in snail_m:
        di = move_d[m_d]
        now = 0
        while now < moving:
            put_x += dx[di]
            put_y += dy[di]
            now += 1
            if nums:
                temp[put_x][put_y] = nums.pop(0)
            else:
                flag = 1
                break
        if flag == 1:
            break
        m_d = (m_d + 1) % 4

    graph = deepcopy(temp)


time = 0
while time < M:

    # 1. 얼음파편던져서 얼음꺠기
    m_d, m_s = magic[time]
    nx = shark_x + dx[m_d]
    ny = shark_y + dy[m_d]

    for move in range(m_s):
        graph[nx][ny] = 0
        nx += dx[m_d]
        ny += dy[m_d]
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            break

    # 2. 달팽이모양으로 이동해주면서 정렬해주기
    snail_move()
    # print(graph)
    # 3. 달팽이 모양으로 돌면서 같은거 4개이상 파괴
    snail_move_2()
    # print(graph)
    # 4. 그룹화시키기
    g()

    # print(graph)

    time += 1

answer = one_bom + (two_bom * 2) + (three_bom * 3)
print(answer)

이 코드가 94퍼에서 틀렸습니다가 떴던 이유는

달팽이돌리면서 터트려주는 부분

(snail_move_2)에서 

""로 주석처리한 저 부분이 문제였습니다.

저는 코드 시간을 줄이기 위해

0을 만나면 나가버리도록 코드를 구성했습니다.

그러자, 다음 그림에서 보인 문제가 발생했습니다.

1이 연속으로 이어져있는 상황인데

0을 만났기 때문에 out해버려서

1이 터지지 않았습니다.

정말 사소한 문제였는데....

이렇게라도 수정을 해서 다행이네요.

 

(추가업데이트:2022.10/13)

dx=[-1,1,0,0]
dy=[0,0,-1,1]
sdir=[2,1,3,0]

def grouping():
    global room
    nx, ny = sx, sy
    dir = 0
    g_list=[]
    now=0
    g_cnt=0
    #먼저 리스트에 다 넣어준다
    for move in snail_move:
        sd = sdir[dir]
        cnt = 0
        dir = (dir + 1) % 4

        while cnt < move:
            nx += dx[sd]
            ny += dy[sd]
            cnt += 1

            if now==0:
                now=room[nx][ny]
                g_cnt=1

            elif now>0 and now==room[nx][ny]:
                g_cnt+=1

            elif now>0 and now!=room[nx][ny]:
                # print(g_cnt,now)
                g_list.append(g_cnt)
                g_list.append(now)
                now=room[nx][ny]
                g_cnt=1

    # print(g_list)
    #초기화 시켜주고
    #받아준데로 다시 넣어주기
    room=[[0]*N for _ in range(N)]
    nx, ny = sx, sy
    dir = 0
    flag=False
    #먼저 리스트에 다 넣어준다
    for move in snail_move:

        sd = sdir[dir]
        cnt = 0
        dir = (dir + 1) % 4

        while cnt < move:
            nx += dx[sd]
            ny += dy[sd]
            cnt += 1
            if g_list:
                now=g_list.pop(0)
                room[nx][ny]=now
            else:
                flag=True
                break

        if flag:
            break





def bomb():
    bom=False

    while True:
        nx, ny = sx, sy
        dir = 0
        now=0
        same_count=0
        same=[]
        for move in snail_move:
            sd = sdir[dir]
            cnt = 0
            dir = (dir + 1) % 4
            while cnt < move:
                nx += dx[sd]
                ny += dy[sd]
                cnt += 1
                if now==0:
                    now=room[nx][ny]
                    same_count=1
                    same.append((nx,ny))
                elif now>0 and now==room[nx][ny]:
                    same_count+=1
                    same.append((nx,ny))

                elif now>0 and now!=room[nx][ny]:
                    if same_count>=4:
                        #print('bom!',same_count,now)
                        bom=True
                        for _ in range(same_count):
                            px,py=same.pop(0)
                            ball[room[px][py]]+=1
                            room[px][py]=0
                    same.clear()
                    same_count=1
                    same.append((nx,ny))
                    now=room[nx][ny]
        #print('re?',bom)
        if bom==True:
            #print('go!')
            sorting()
            bom=False
        else:
            break

def sorting():
    nx,ny=sx,sy
    dir=0
    flag=False

    past=[]
    #이전의 좌표를 past에 담음
    for move in snail_move:
        sd=sdir[dir]
        cnt=0
        while cnt<move:
            nx+=dx[sd]
            ny+=dy[sd]
            cnt+=1
            if not flag and room[nx][ny]==0:
                #처음 0을 만나면 past를 새로 넣어주고 슬슬 가동시켜준다
                flag=True
                past.append((nx,ny))

            elif flag and not room[nx][ny]==0:
                #0이 아닌걸 만났다면, 현재 past에 넣어준 맨 앞의 거랑 바꿔준다
                px,py=past.pop(0)
                room[px][py],room[nx][ny]=room[nx][ny],room[px][py]
                past.append((nx,ny))


            elif flag and room[nx][ny]==0:
                #새로운 0을 만났다면, 현재 past자리 뒤에 하나만 더 채워주기
                #맨 앞에 있었던 거는 다음 0을 만나야 빼진다
                #만약 0을 계속 만난다면 past는 언제든지 계속 채워짐
                past.append((nx,ny))


        dir=(dir+1)%4
    # for k in range(N):
    #     print(room[k])
    # print()


def inside(x,y):
    if x<0 or x>=N or y<0 or y>=N:
        return False
    return True

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

room=[list(map(int,input().split())) for _ in range(N)]
command=[]
for _ in range(M):
    d,s=map(int,input().split())
    command.append((d-1,s))

snail_move=[]
for i in range(1,N):
    snail_move.append(i)
    snail_move.append(i)

snail_move.append(N-1)

sx,sy=N//2,N//2
ball=[0,0,0,0]
#먼저 명령대로 터트리기
for nd,ns in command:
    nx,ny=sx,sy
    for r in range(ns):
        nx+=dx[nd]
        ny+=dy[nd]
        if not inside(nx,ny):
            break

        room[nx][ny]=0

    # for k in range(N):
    #     print(room[k])
    # print()
    #달팽이 이동 돌면서 0인 자리 매워주기
    sorting()
    #구슬폭발
    bomb()
    # for k in range(N):
    #     print(room[k])
    # print()

    #집단화
    grouping()

    # for k in range(N):
    #     print(room[k])
    # print()
now_score=ball[1]+2*ball[2]+3*ball[3]
print(now_score)

 

문제를 좀 더 깔끔하게 풀어봤습니다.

달팽이를 역순으로 다시 꺽는 걸 구현할 수는 있는데

구현난이도를 스스로 높인 느낌이었습니다.

그래서 사라진 거 정렬해줄 때

미리미리 지나갔던 좌표들을 넣어줬습니다.

만약 0을 처음 만났다면

전에 집어넣었던 걸 바로 꺼내겠죠?

그러다가 다시 0을 만난다면(다시 부셔진 지역)

이전 좌표에 해당 좌표를 입력하고 다음 좌표로 넘어갑니다.

그럼 맨 앞의 좌표는

그 다음에 0을 만나지 않으면 꺼내어서 사용.

0이 하나만 만나면

리스트 pop(0)를 하면 이전에 넣어준 걸 바로 받습니다.

그러다가 0을 하나 더 만나면

리스트에 추가해고 pop은 하지 않습니다.

그럼 다음에 pop(0)를 하면

전전에 만난 걸 꺼내게 되니

0이 2번 밀려난 만큼 정렬이 되는 식입니다.

(코드를 보시면서 그림을 그리시면 이해가 더 빠를 겁니다.)

그리고 그룹군은 

그룹군을 순서대로 구하고

아예 room을 0으로 초기화한 다음에

그룹군 순서대로 하나하나씩 다 넣어줬습니다.

만약 그룹군을 다 썼다면 반복을 멈춰주고요.