백준 21611 파이썬

강한개발자·2021년 10월 16일
0

코딩왕이 되기 위해

목록 보기
15/15

문제

마법사 상어와 블리자드

백준 21611 바로가기

코테 시즌 기념 삼성 기출문제를 풀어봤다.
이거 푸는데 거의 3시간 정도 걸렸다. 미친 난이도는 아니지만,, 노트 안쓰고 풀려니 머리속이 뒤죽박죽..

풀이

상어는 정말 대단하다. 어떻게 이렇게 귀찮게 문제를 낼 수가 있지

요구사항

  1. 얼음날려서 특정 배열 위치의 숫자 0으로 바꾸기
  2. 0으로 바꾼 것 배열 특성에 따라 앞으로 채워주기
  3. 배열 특성에 따라 연속되는 4개이상의 수를 0으로 바꿔주기
  4. 0으로 바꾼 것 배열 특성에 따라 앞으로 채워주기
  5. 3번 경우 없을 때 까지 반복하기
  6. 연속되는 수를 그룹으로 묶어 각 그룹별로 몇개인지(A) , 어떤 숫자인지 (1,2,3) 에 따라 새로운 값으로 바꾸기

핵심 : 2차원 배열을 1차원으로 바꾸자

이 문제에서는 나선형? 으로 배열접근해야한다.
그게 너무 싫어서 배열을 1차원배열로 만들어버리는 코드를 구현했다.
배열에서 값을 가져와서 1차원배열로 편하게 수정하고 다시 적용하는 방법을 택했다.
너무 편하다.

1차원 배열로 가져올때 상어 기준으로 멀어지는 방향으로 갖고 온다.

24-> 23 -> 22 -> 21 ... 순으로 갖고오기때문에 나중에 뒤에서 부터 계산해야 할 수 있다.

그래서 나는 갖고 온 배열 다시 역순처리해줬다.

처음 갖고 올 때부터

from collections import deque
deq=deque()
deq.appendleft()

사용해 주면 역순 처리 안해줘도 된다. 이 방법이 더 편했을 듯?
매번 역순처리해주느라 헷갈려서 한 시간 정도 낭비한것같다.

정신이 나갈 뻔 했다

1차원 배열로 바꿔서 풀면
요구사항 2,3,4 5,6 전부 1차원배열 탐색 하면서 값바꾸는 아주 쉬운
solved.ac 기준 실버 정도의 문제라고 생각된다.

주의

코드가 굉장히 복잡하니 보시는 분이 있을진 모르지만,,, 보는 사람은 잘 파악하길 바랍니다.
나름 함수로 구현해놓았지만 쉽지않습니다.

함수 설명

1. cal_biz_list()

flag 값에 따라 원래의 배열에서 1차원 배열로 값 복사/저장 하는 함수 

flag =0 이면 N*N 배열에서 deque로  값 복사 
flag = 1 이면 deque에서 N*N 배열으로 값 복사

2. break_number(d,s)

d와 s를 가지고 얼음을 날려 지울 N*N 배열 위치 찾아 0으로 치환한다. 

3. biz_fill()

중간에 0 이 껴있는 경우 채워주고 앞에 0 없어진만큼 뒤에 0 넣도록 구현 

4. degtroy_biz()

연속된 4자리 수가 있는 경우 없애도록 구현 
없애서 새로 생긴 배열에 또 있을 수 있으므로 
check 변수 사용하여 바뀐 경우 한 번 더 Loop 돌도록 구현 

5. grouping()

1차원 배열에서 값 탐색하며 연속된 그룹의 특성에 따라 새로운 배열 만들도록 구현 
다 만들면 조건에 따라 원래의 배열 값 갱신을 해줌 

정답 코드


#블리자드
from collections import deque
import sys
input=sys.stdin.readline

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

arr=[[0 for _ in range(N+1)]]+[[0]+list(map(int,input().split())) for _ in range(N)]

blizard=[map(int,input().split()) for _ in range(M)]

dx=[0,-1,1,0,0]
dy=[0,0,0,-1,1]
# 1 2 3 4

m_set=[0,0,0,0]
biz_list=deque()
def cal_biz_list(type):
    global biz_list

    s_x=1
    s_y=0
    tmp=N
    # 오른쪽 아래쪽 왼쪽 오른쪽
    # 7 6 6 5 가고
    # 5 4 4 3 가고
    # 3 2 2 1 가고
    cnt_lst=[N,N-1,N-1,N-2]
    cnt_start=0
    di_x=[0,1,0,-1]
    di_y=[1,0,-1,0]
    if type==0:
        # 갖고와서 처리하는 용
        biz_list = deque()
        while 1:
            if s_x==(N+1)//2 and s_y==(N+1)//2 -1 :
                break
            for i in range(4):
                cnt_start+=2
                for k in range(cnt_lst[i]):
                    s_x+=di_x[i]
                    s_y+=di_y[i]

                    biz_list.append(arr[s_x][s_y])
            cnt_lst=[i-2 for i in cnt_lst]
    else:
        # 처리 후 다시 저장하는용
        cnt=0
        while 1:
            if s_x == (N + 1) // 2 and s_y == (N + 1) // 2 - 1:
                break
            for i in range(4):
                cnt_start += 2
                for k in range(cnt_lst[i]):
                    s_x += di_x[i]
                    s_y += di_y[i]

                    arr[s_x][s_y]=biz_list[cnt]
                    cnt+=1
            cnt_lst = [i - 2 for i in cnt_lst]
def break_number(d,s):
    c=[(N+1)//2 , (N+1)//2]
    for i in range(1,s+1):
        c[0]+=dx[d]
        c[1]+=dy[d]
        arr[c[0]][c[1]]=0

def biz_fill():
    global biz_list
    biz_list_tmp=deque()
    cnt=0
    for i in range(N*N-1):
        if biz_list[i]!=0:
            biz_list_tmp.append(biz_list[i])
        else:
            cnt+=1
    for _ in range(cnt):
        biz_list_tmp.append(0)

    biz_list=biz_list_tmp

def destroy_biz():
    global biz_list,m_set
    while_check=1

    while while_check==1:
        # 폭발시키기 위해 arr에서 가져오기
        cal_biz_list(0)
        # 같은 숫자 지우기 위해 역순
        biz_list.reverse()
        while_check=0
        cnt=1
        tmp=biz_list[0]
        start=0
        for i in range(1,len(biz_list)):
            if biz_list[i]==tmp:
                cnt+=1
            else:
                if cnt>=4:
                    while_check=1

                    m_set[biz_list[start]]+=cnt
                    for k in range(start,i):
                        biz_list[k]=0

                cnt=1
                start=i
                tmp=biz_list[i]
        # 이 시점에서 biz fill 8개 삭제되어야함

        # 0 지우고 뒤에 채워넣기
        biz_fill()
        # 채워넣기전 돌리기
        biz_list.reverse()
        # 다시 넣기
        cal_biz_list(1)


def grouping():
    global biz_list
    biz_list_tmp=deque()
    # arr -> biz_list 로 갖고와서  00 이 먼저
    cal_biz_list(0)
    # biz list 역순으로 돌리고 (돌리는 이유는 채우기 용)
    biz_list.reverse()

    cnt=1
    tmp=biz_list[0]
    for i in range(1,len(biz_list)):
        # 연속그룹일때
        if tmp==biz_list[i]:
            cnt+=1
        else:
            # 다른게 나왔을 때 현재까지 기준으로 append
            biz_list_tmp.append(cnt)
            biz_list_tmp.append(tmp)

            tmp=biz_list[i]
            cnt=1
        if len(biz_list_tmp) > N*N:
            break
    while 1:
        if len(biz_list_tmp)>N*N-1:
            break
        biz_list_tmp.append(0)

    biz_list=deque(biz_list_tmp[i] for i in range(N*N-1))

## 블리자드 처리
for d,s in blizard:

    # arr에서 삭제하고
    break_number(d,s)

    # arr -> biz_list 로 갖고와서  00 이 먼저
    cal_biz_list(0)
    # biz list 역순으로 돌리고 (돌리는 이유는 채우기 용)
    biz_list.reverse()
    # 0 지우기
    biz_fill()
    # 채워넣기 전 돌리기
    biz_list.reverse()
    # 다시 채워넣기
    cal_biz_list(1)


    # 연속폭발

    destroy_biz()

    # 그룹 지어서 append 하기
    grouping()
    # 다시 arr 에 넣어야한다. 앞자리 부 터 시작하는중
    biz_fill()
    biz_list.reverse()
    # 다시 채워넣기
    cal_biz_list(1)

print(m_set[1]+m_set[2]*2+m_set[3]*3)

결과 정답

profile
강한친구의 코딩 성장기

0개의 댓글