[#11559] 뿌요뿌요

RookieAND·2022년 7월 12일
0

BaekJoon

목록 보기
27/42
post-thumbnail

❓ Question

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

📖 Before Start

BFS 탐색을 사용하되, 문제에서 요구하는 기능을 잘 구현해야 하는 문제였다.

이번 문제는 그래프 이론을 활용하여 작은 게임 시스템을 구현해야 하는 문제였다.
구현에 필요한 기능을 나열한 후, 이를 토대로 코드를 작성하여 정답을 맞추었다.

✒️ Design Algorithm

뿌요뿌요 게임 시스템이 요구하는 기능을 알맞게 구현해보자.

가로 6 줄, 세로 12 줄의 이차원 배열에 총 다섯 종류의 뿌요가 배치되어 있다.
여기서 뿌요뿌요 게임을 제작하기 위해 구현해야 할 기능은 아래와 같다.

  1. 같은 색의 뿌요가 4개 이상 상하좌우로 연결되어 있으면 이를 모두 제거해야 한다.
  2. 제거 가능한 뿌요들이 여러개가 있다면 동시에 제거하고, 한 번의 콤보로 인정한다.
  3. 뿌요들을 제거한 후, 아래에 빈 공간이 있는 뿌요들은 전부 밑으로 내려야 한다.

따라서 게임의 진행 흐름은 뿌요 제거 - 필드 정리 - 콤보 추가 순으로 진행될 것이다.
그런 뒤, 총 몇 번의 콤보가 쌓였는지를 최종적으로 판단하여 출력시키면 끝이다.

💻 Making Own Code

✅ Correct Code

import sys
from collections import deque

read = sys.stdin.readline
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
field = [list(read().strip()) for _ in range(12)]

# 필드의 가로, 세로 값을 담은 변수 N, M
N, M = 12, 6

def remove_puyo(y, x, color):
    queue = deque([(y, x)])
    puyos = [(y, x)]
    while queue:
        ny, nx = queue.popleft()
        for direct in direction:
            my, mx = ny + direct[0], nx + direct[1]
            if 0 <= my < N and 0 <= mx < M:
                if field[my][mx] == color and (my, mx) not in puyos:
                    queue.append((my, mx))
                    puyos.append((my, mx))

    # 만약 인접한 동일 색상 뿌요가 4개 이상이라면, 이를 제거함.
    if len(puyos) >= 4:
        for ly, lx in puyos:
            field[ly][lx] = '.'
        return True

    return False


# 뿌요 밑에 빈 공간이 있을 경우, 뿌요를 아래로 내리는 방법.
def set_field():
    # 10 줄부터 0 줄까지, 역순으로 빈 공간이 있는지를 탐색함.
    for y in range(N - 2, -1, -1):
        for x in range(M):
            if field[y][x] != '.':
                d = 1
                # 바로 아랫줄이 유효 구역 내에 있고, 빈 공간이라면 위치 변경.
                while y + d < N and field[y + d][x] == '.':
                    # 바로 아랫줄에 위치한 빈 공간과 현재 뿌요의 위치를 바꾸는 수식.
                    field[y + d][x], field[y + d - 1][x] = field[y + d - 1][x], field[y + d][x]
                    d += 1


# 필드를 순회하면서, 제거가 가능한 뿌요 덩어리가 있는지를 판별하는 함수.
def find_puyo():
    can_combo = False
    for i in range(N):
        for j in range(M):
            if field[i][j] == '.':
                continue
            if remove_puyo(i, j, field[i][j]):
                can_combo = True

    return can_combo


combo = 0
while True:
    # 제거 가능한 뿌요 덩어리가 있는지를 판별.
    if not find_puyo():
        break
    set_field()
    combo += 1
print(combo)

게임 시스템을 정확히 구현하였는지에 대한 여부가 상당히 중요했다.

먼저, 필드 위에 놓인 뿌요들 중 제거 가능한 뿌요가 있는지를 먼저 판별해야 했다.
따라서 find_puyo 함수를 통해 필드에 제거 가능한 뿌요가 있는지를 체크하였다.
그리고 뿌요들을 제거하기 위한 함수로 remove_puyo 함수를 추가적으로 만들었다.

여기서 중요한 점은, 먼저 뿌요를 제거한 후에 필드를 정리해야 한다는 것이다.
만약 뿌요를 제거한 직후 남은 뿌요들을 아래로 내리게 된다면 진행이 꼬이게 된다.
따라서 제거 가능한 뿌요들을 없애고 난 뒤에, 남은 뿌요들을 아래로 내려야 한다.


추가적으로, 남은 뿌요를 밑으로 내리는 로직은 아래와 같이 구현하였다.

  1. 이차원 배열 중에서 10줄 부터 0줄까지의 공간 중, 뿌요가 든 공간을 체크함.
  2. 해당 공간에 뿌요가 있는지, 그리고 아랫줄의 공간도 마저 비었는지를 판별함.
  3. 만약 아랫줄이 비었다면, 위치를 변경하고 그 다음 줄에 대한 탐색을 진행함.

설명으로 쓰려니까 참 어렵긴 하다. 코드를 보면서 부디 이해가 되었으면 좋겠다.

📖 Conclusion

https://github.com/RookieAND/BaekJoonCode

간만에 풀어보는 구현 문제인데, 역시 생각할 게 참 많다는 것을 다시금 느낀다.

profile
항상 왜 이걸 써야하는지가 궁금한 사람

0개의 댓글