BFS 탐색을 사용하되, 문제에서 요구하는 기능을 잘 구현해야 하는 문제였다.
이번 문제는 그래프 이론을 활용하여 작은 게임 시스템을 구현해야 하는 문제였다.
구현에 필요한 기능을 나열한 후, 이를 토대로 코드를 작성하여 정답을 맞추었다.
뿌요뿌요 게임 시스템이 요구하는 기능을 알맞게 구현해보자.
가로 6
줄, 세로 12
줄의 이차원 배열에 총 다섯 종류의 뿌요가 배치되어 있다.
여기서 뿌요뿌요 게임을 제작하기 위해 구현해야 할 기능은 아래와 같다.
따라서 게임의 진행 흐름은 뿌요 제거 - 필드 정리 - 콤보 추가 순으로 진행될 것이다.
그런 뒤, 총 몇 번의 콤보가 쌓였는지를 최종적으로 판단하여 출력시키면 끝이다.
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
함수를 추가적으로 만들었다.
여기서 중요한 점은, 먼저 뿌요를 제거한 후에 필드를 정리해야 한다는 것이다.
만약 뿌요를 제거한 직후 남은 뿌요들을 아래로 내리게 된다면 진행이 꼬이게 된다.
따라서 제거 가능한 뿌요들을 없애고 난 뒤에, 남은 뿌요들을 아래로 내려야 한다.
추가적으로, 남은 뿌요를 밑으로 내리는 로직은 아래와 같이 구현하였다.
설명으로 쓰려니까 참 어렵긴 하다. 코드를 보면서 부디 이해가 되었으면 좋겠다.
https://github.com/RookieAND/BaekJoonCode
간만에 풀어보는 구현 문제인데, 역시 생각할 게 참 많다는 것을 다시금 느낀다.