145. [삼성기출41]Python 백준 21611 마법사 상어와 블리자드

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 21611 마법사 상어와 블리자드 입니다.

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

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

 

문제 접근

먼저 이 문제는 일반적인 배열 접근 순서가 아닌 순서로 접근해야 됬다.

매번 좌표를 계산하기 힘드므로 맨 처음부터 index와 맞는 좌표를 구해 저장해서 문제를 푸는동안 계속 사용했다.

내가 발견한 이동 규칙은 다음과 같다.

1. 하, 우, 상, 좌 순으로 방향이 계속 바뀐다.

2. 이동하는 거리는 1부터 시작해서 방향이 두번 바뀔때마다, 1씩 늘어나다가 최종적으로 (0, 0) 에 도착하면

늘어나는 것을 멈췄다.

위 두가지의 규칙을 기반으로 다음과 같은 코드를 작성했다.

def make_coordinate():#이동경로 만들기
    length = 1
    d = 0
    x, y = s_x, s_y
    while True:
        for _ in range(2):
            for _ in range(length):
                x, y = dx[d] + x, dy[d] + y
                if y == -1:
                    return
                coordinates.append((x, y))
            d = (d + 1) % 4
        length += 1

 

1. 빈칸 채우기

좌표를 순서대로 돌면서 빈칸이 있다면 빈칸이 아닌 가장 가까운 블럭을 가져오는 식으로 코드를 구현했다.

빈칸을 채우는 index A, 빈칸이 아닌 가장 가까운 블럭의 index B각 한개씩 선언했고, 코드에 따라 이 순서가 역전될 수 있는데

A가 B를 역전하면 B = A + 1로 보정해줬다. 앞서 좌표들을 coordinates에 미리 저장해놨기 때문에 두 index들을 이용하여 비교적 자유롭게 블럭을 이동시킬 수 있었다.

def fill_blank():
    coord_index = 1
    for index, (x, y) in enumerate(coordinates):
        if index > coord_index:
            coord_index = index + 1
        if board[x][y] == 0:
            nx, ny = coordinates[coord_index]
            while board[nx][ny] == 0:
                coord_index += 1
                if coord_index > N**2 - 2:
                    return
                nx, ny = coordinates[coord_index]
            board[x][y] = board[nx][ny]
            board[nx][ny] = 0

 

2. 폭발

index를 증가시키면서 이전 색과 현재 index가 위치하는 색이 같다면 same_cnt를 증가시켰다.

또한 탐색할 좌표들을 same_color_coord에 저장했다.

만약 same_cnt가 4 이상이라면 

same_color_coord안의 좌표들을 모두 0으로 만들고 same_cnt, same_color_coord를 새로운 좌표 부터 다시 시작했다.

 

만약 4 이하라면 폭발시키지 않고 

same_cnt, same_color_coord를 새로운 좌표 부터 다시 시작했다.

 

3. 구슬 변화

위와 같은 방식으로 같은 색 개수, 구슬 정보를 받아 new_marbles에 저장했고

저장할 구슬이 없거나 board크기를 벗어나면 저장하는걸 멈추고

아까 만든 좌표 순서대로 new_marbles의 데이터를 board에 새로 넣어줬다.

 

Python 정답 코드

백준 21611 마법사 상어와 블리자드 코드입니다. 설명은 아래에 있습니다.

 

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
casts = [list(map(int, input().split())) for _ in range(M)]
dx = (0, 1, 0, -1)
dy = (-1, 0, 1, 0)
bdx = (-1, 1, 0, 0)
bdy = (0, 0, -1, 1)
s_x, s_y = N//2, N//2
board[s_x][s_y] = 4
coordinates = []
one = 0
two = 0
three = 0

def debug():
    for i in range(N):
        for j in range(N):
            print(board[i][j], end=" ")
        print()
    print()

def make_coordinate():#이동경로 만들기
    length = 1
    d = 0
    x, y = s_x, s_y
    while True:
        for _ in range(2):
            for _ in range(length):
                x, y = dx[d] + x, dy[d] + y
                if y == -1:
                    return
                coordinates.append((x, y))
            d = (d + 1) % 4
        length += 1

def blizzard(d, s):
    for i in range(1, s + 1):
        nx, ny = bdx[d - 1]*i + s_x, bdy[d - 1]*i + s_y
        board[nx][ny] = 0

def fill_blank():
    coord_index = 1
    for index, (x, y) in enumerate(coordinates):
        if index > coord_index:
            coord_index = index + 1
        if board[x][y] == 0:
            nx, ny = coordinates[coord_index]
            while board[nx][ny] == 0:
                coord_index += 1
                if coord_index > N**2 - 2:
                    return
                nx, ny = coordinates[coord_index]
            board[x][y] = board[nx][ny]
            board[nx][ny] = 0

def explode():
    global one, two, three
    x, y = coordinates[0]
    before_color = board[x][y]
    index = 1
    same_cnt = 1
    same_color_coord = [(x, y)]
    exploded = False
    while index < N**2 - 1:
        x, y = coordinates[index]
        if before_color == board[x][y]:
            same_color_coord.append((x, y))
            same_cnt += 1
        else:
            if same_cnt >= 4:
                exploded = True
                for nx, ny in same_color_coord:
                    board[nx][ny] = 0
                if before_color == 1:
                    one += same_cnt
                elif before_color == 2:
                    two += same_cnt
                elif before_color == 3:
                    three += same_cnt

            before_color = board[x][y]
            same_color_coord = [(x, y)]
            same_cnt = 1

        index += 1
    return exploded

def change():
    x, y = coordinates[0]
    before_color = board[x][y]
    total_diff_colors = 0
    index = 1
    same_cnt = 1
    new_marbles = []
    while index < N**2 - 1:
        if 2 * total_diff_colors > N**2 - 1:
            break
        x, y = coordinates[index]
        if before_color == board[x][y]:
            same_cnt += 1
        else:
            new_marbles.append(same_cnt)
            new_marbles.append(before_color)
            before_color = board[x][y]
            same_cnt = 1
        index += 1

    len_new_marbles = len(new_marbles)
    for index, (x, y) in enumerate(coordinates):
        if index >= len_new_marbles:
            break
        board[x][y] = new_marbles[index]

def solve():
    make_coordinate()
    iteration = 0
    for d, s in casts:
        iteration += 1
        blizzard(d, s)
        fill_blank()

        while True:
            if not explode():
                break
            fill_blank()
        change()
    return one + 2*two + 3*three

print(solve())

 

백준 21611 마법사 상어와 블리자드 Python 코드였습니다.

감사합니다.