[백준 삼성기출 △] 마법사 상어와 블리자드(python)

이진규·2022년 10월 9일
1

백준(PYTHON)

목록 보기
93/115

문제

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

나의 코드

"""

"""

"""
0. 격자판 배치
  1. 구슬 파괴
    2. 2차원 배열을 1차원 배열로 변환
    3. 구슬 이동
    4. 구슬 폭발
    -> 3, 4의 과정을 더 이상 구슬이 폭발하지 않을 때(연속하는 구슬의 번호가 4개 미만)까지 반복
  5. 구슬 변화
  6. 1차원 배열을 2차원 배열로 다시 변환
  -> 1 ~ 6의 과정을 M만큼 반복
7. 폭발한 구슬을 점수화 해서 출력
"""

N, M = map(int, input().split()) # N:격자판 크기, M:마법 횟수
pan = [ list(map(int, input().split())) for _ in range(N) ] # 격자판
magic = [ list(map(int, input().split())) for _ in range(M) ] # 블리자드의 마법
s_x, s_y = N//2, N//2 # 상어의 좌표
pan[s_x][s_y] = -1 # 상어 : -1로 표시 (빈칸 : 0, 구슬 : 1, 2, 3)
answer = 0

dx = [-1, 1, 0, 0] # 상, 하, 좌, 우
dy = [0, 0, -1, 1]
def bead_destroy(d, s): # 구슬을 파괴하는 함수

    x, y = s_x, s_y
    for _ in range(s):
        mx = x + dx[d]
        my = y + dy[d]

        pan[mx][my] = 0

        x, y = mx, my

def bead_2d_1d(arr_2d): # 2차원 배열을 1차원 배열로 변환

    d_dx, d_dy = [0, 1, 0, -1], [-1, 0, 1, 0]
    visited = [ [False] * N for _ in range(N) ]
    arr_1d = []
    x, y = s_x, s_y
    dir = -1

    while True:

        visited[x][y] = True
        arr_1d.append(arr_2d[x][y])
        if x == 0 and y == 0:
            break

        md = (dir + 1) % 4
        mx = x + d_dx[md]
        my = y + d_dy[md]

        if visited[mx][my] == True: # 만약 방문한 곳이라면 방향을 꺾지말고 이전 방향 그대로 직진
            md = dir
            mx = x + d_dx[md]
            my = y + d_dy[md]

        x, y, dir = mx, my, md

    return arr_1d

def bead_move(arr): # 빈자리를 채우는 구슬의 이동
    tmp = []

    for x in arr:
        if x > 0:
            tmp.append(x)

    return tmp

def bead_bomb(arr): # 구슬의 폭발 함수 + 폭발한 구슬의 개수에 대한 점수 계산
    global answer

    flag = False # 구슬이 폭발한다면 True, 폭발하지 않았다면 False
    n = len(arr)
    num = 0 # 연속하는 구슬의 번호
    cnt = 1 # 연속하는 구슬의 개수
    for i in range(n-1):
        if arr[i] == arr[i+1]:
            num = arr[i]
            cnt += 1
        else:
            if cnt >= 4:
                arr[i-cnt+1:i+1] = [0]*cnt # 구슬 폭발
                answer += (num * cnt) # 구슬 폭발에 따른 점수 계산
                flag = True
            cnt = 1

    if cnt >= 4:
        arr[n-cnt+1:n+1] = [0]*cnt
        answer += (num * cnt)
        flag = True

    return arr, flag

def bead_motivation(arr): # 구슬의 변화를 시켜주는 함수

    tmp = []
    n = len(arr)
    cnt = 1

    if not arr: # 만약 빈 구슬만 들어오는 경우 빈 배열로 반환
        return tmp

    for i in range(n-1): # 1 ~ n-1까지 구슬의 변화를 시켜줌
        if arr[i] == arr[i+1]:
            cnt += 1
        else:
            tmp.append(cnt)
            tmp.append(arr[i])
            cnt = 1

    if cnt >= 2: # 만약 n-2에서 cnt += 1만 하고 끝나는 경우 마지막 배열 원소를 세기위해 이렇게 반복문 구성
        tmp.append(cnt)
        tmp.append(arr[n-1])
    else: #
        tmp.append(cnt)
        tmp.append(arr[n-1])

    return tmp

def bead_1d_2d(arr_1d): # 1차원 배열을 2차원 배열로 변환

    # 만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다 -> 구현하기 위해 범위 제한
    n = N**2-1 if len(arr_1d) > N**2-1 else len(arr_1d)

    d_dx, d_dy = [0, 1, 0, -1], [-1, 0, 1, 0]

    arr_2d = [ [0] * N for _ in range(N) ]
    visited = [ [False] * N for _ in range(N) ]

    arr_2d[s_x][s_y] = -1
    x, y = s_x, s_y
    dir = -1

    for i in range(n):

        visited[x][y] = True

        md = (dir + 1) % 4
        mx = x + d_dx[md]
        my = y + d_dy[md]

        if visited[mx][my] == True:
            md = dir
            mx = x + d_dx[md]
            my = y + d_dy[md]

        arr_2d[mx][my] = arr_1d[i]
        x, y, dir = mx, my, md

    return arr_2d

for d, s in magic:
    bead_destroy(d-1, s) # 구슬 파괴

    pan_1d = bead_2d_1d(pan) # 2차원 배열 -> 1차원 배열

    # print(pan_1d)

    pan_1d = bead_move(pan_1d) # 빈자리를 채우기 위한 구슬의 이동

    # print(pan_1d)

    while True:
        pan_1d, flag = bead_bomb(pan_1d) # 구슬의 폭발

        if flag == True: # 폭발한 곳은 0으로 채웠기 때문에 다시 구슬의 이동 필요
            pan_1d = bead_move(pan_1d) # 빈자리를 채우기 위한 구슬의 이동
        else: # 폭발하지 않았다면 더 이상 폭발할 곳이 없는것을 의미하므로 반복문 탈출
            break

    # print(pan_1d)

    pan_1d = bead_motivation(pan_1d) # 구슬의 변화

    # print(pan_1d)

    pan = bead_1d_2d(pan_1d) # 1차원 배열로 변환했던 것을 다시 2차원 배열로 변환

    # for i in pan:
    #     print(i)

print(answer)
    

설명

  1. 구슬 변화 부분에서 빈 구슬만 들어오는 경우 처리를 따로 해주어야함 (히든 케이스 고려)

    3 1
    0 0 0
    0 0 0
    0 0 0
    1 1

  2. 구슬이 폭발할 때 반복문 구성에서 마지막 인덱스 까지 깔끔하게 처리해야 함

    if cnt >= 4:
    arr[n-cnt+1:n+1] = [0]cnt
    answer += (num
    cnt)
    flag = True

        
  3. ★ 2차원 배열을 1차원 배열로, 1차원 배열을 2차원 배열로 변환 시키는 아이디어 생각

참고 자료

profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글