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

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

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

문제 설명

문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.

이 문제는, 특별한 알고리즘 없이 문제에서 주어진 사항을 구현하는 문제이지만

구현해야 하는 부분들이 굉장히 까다로운 문제였습니다

---

풀이 과정

풀이과정이 굉장히 길기 때문에, 잘 모르시는 부분을 중점으로 보시는 것을 추천드립니다.

 

① 먼저, 가운데 칸(n//2, n//2)은 상어가 있는 곳이며 여기를 시작으로 하여 토네이도처럼 돌아

각 칸에 인덱스를 붙여줘야 한다.(1, 2, 3... n*n)

이 부분은 indexing함수에서 구현하였다.

 

② 그리고 상어가 마법을 시전하는데, 이 부분은 magic함수에 구현하였다.

위 아래 왼쪽 오른쪽 4방향중에 1방향과 거리가 주어지며

마법 후 해당 칸의 숫자는 사라진다.

해당칸을 0으로 표현함으로써 사라졌음을 표시하였다.

 

③ 사라진 후에는 빈 칸만큼 뒷 칸들이 당겨야 하기 때문에 이부분은 fill_blank 함수에 구현하였다.

1번 칸부터 순서대로 돌면서 0인 칸(즉, 빈칸)을 발견하면 그 칸을 blankIdx라는 큐에 넣어준 상태로

빈 칸을 만나지 않았을 때, 큐에서 빈칸의 인덱스를 꺼내어

그 칸에 현재 칸의 수를 넣어주고, 현재 칸은 0으로(빈 상태) 만들어줌으로써 당겨주었다.

모두 당겨질 때 까지 반복한다.

 

④ 이제, 연속된 숫자가 4칸 이상 존재한다면 그 칸들을 폭발시킨다.

이 부분은 bomb 함수에 구현하였다.

처음에는 저장할 숫자가 없으므로 임시로 -1을 지정하였고

칸을 돌면서 전 칸과 같은 숫자가 발생한다면 카운트를 늘려나간다.

그러다가 저장하고 있는 숫자와 다른 수를 만났을 때, 저장하고 있는 수의 카운트가 4 이상이라면 폭발해야하므로

그 칸들을 모두 0으로 바꿔준다. 그리고 점수계산을 해야 하므로 점수도 함께 저장한다.

 

⑤ 폭발 후에는 그룹을 지어야 한다.

이 부분은 grouping 함수에 구현하였다.

 

from collections import deque

n, m = map(int, input().split())
graph = []
cmd = []
score = [0]*3

def indexing():
    x, y = n // 2, n // 2
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    depth = 0

    while True:
        for i in range(4):
            if i % 2 == 0:
                depth += 1
            for j in range(depth):
                x += dx[i]
                y += dy[i]
                graphIdx.append((x, y))
                if x == 0 and y == 0:
                    return


def magic(dir, dist):
    x, y = n // 2, n // 2
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(dist):
        x += dx[dir]
        y += dy[dir]
        if x < 0 or x >= n or y < 0 or y >= n:
            break
        graph[x][y] = 0

    fill_blank()
    while bomb():
        fill_blank()
    grouping()


def fill_blank():
    blankIdx = deque()
    for x, y in graphIdx:
        if graph[x][y] == 0:
            blankIdx.append((x, y))
        elif graph[x][y] > 0 and blankIdx:
            nx, ny = blankIdx.popleft()
            graph[nx][ny] = graph[x][y]
            graph[x][y] = 0
            blankIdx.append((x, y))


def bomb():
    visited = deque()
    cnt = 0
    num = -1
    flag = False
    for x, y in graphIdx:
        if num == graph[x][y]:
            visited.append((x, y))
            cnt += 1
        else:
            if cnt >= 4:
                score[num-1] += cnt
                flag = True

            while visited:
                nx, ny = visited.popleft()
                if cnt >= 4:
                    graph[nx][ny] = 0

            num = graph[x][y]
            cnt = 1
            visited.append((x, y))

    return flag


def grouping():
    cnt = 1
    tmpx, tmpy = graphIdx[0]
    num = graph[tmpx][tmpy]
    nums = []

    for i in range(1, len(graphIdx)):
        x, y = graphIdx[i][0], graphIdx[i][1]
        if num == graph[x][y]:
            cnt += 1
        else:
            nums.append(cnt)
            nums.append(num)
            num = graph[x][y]
            cnt = 1

    idx = 0
    for x, y in graphIdx:
        if not nums:
            break
        graph[x][y] = nums[idx]
        idx += 1
        if idx == len(nums):
            break

for i in range(n):
    graph.append(list(map(int, input().split())))

for i in range(m):
    d, s = map(int, input().split())
    cmd.append((d, s))

graphIdx = deque()
indexing()

for a, b in cmd:
    magic(a-1, b)

answer = 0
for i in range(3):
    answer += (i+1) * score[i]

print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !