문제 링크
예전에 스팀에서 뿌요뿌요 게임 했던 걸 생각하며 즐겁게 들어갔는데 그걸 진짜 알고리즘으로 짜려니 신경써야 할 것도 많고ㅎㅎ,, 까다로웠다. 구현 문제들이 으레 그렇듯 이 문제도 테케 통과해서 돌려보면 틀리고 질문 검색에서 반례를 뒤지고 나서야 뭐가 틀린지 깨달았던 문제이다. 이런 문제 실전에서 반례 어떻게 생각하는지....... 허헝ㅜㅜ
먼저 입력값을 받는 부분은 다음과 같다.
from collections import deque
import sys, copy
input = sys.stdin.readline
field = []
visited = [[0]*6 for _ in range(12)]
for i in range(12):
field.append(list(input().rstrip()))
field.reverse()
ans = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]입력값으로 받은 field값은 reverse로 순서를 바꾸어준다..! 원소의 순서가 바꾸어지는 것이 아니라 자리가 바뀌는 것이므로 정답에 영향이 없다. 이렇게 바꾸어주어야 탐색할 때 인덱스 값을 정하는데 쉽다.
그리고 같은 원소가 4개 이상 모이면 폭파시키는 dumb()함수를 만들어준다.
def bumb(color):
global field, visited
cnt = 0
field2 = copy.deepcopy(field)
visited2 = copy.deepcopy(visited)
while q:
x, y = q.popleft()
visited2[x][y] = 1
field2[x][y] = '.'
cnt += 1
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < 12 and 0 <= ny < 6:
if not visited2[nx][ny] and field[nx][ny] == color:
q.append((nx, ny))
if cnt >= 4:
field = copy.deepcopy(field2)
return True
else:
visited = copy.deepcopy(visited2)
return False(위 아래, 양 옆을 탐색할 때 인덱스값을 검사해주는 것 까먹지말자)
깊은 복사를 이용하여 field 와 visited를 수정해주었다. 만약 같은 색깔이 4개 이상이라 폭파시켜야하면 수정했던 field를 할당해주고, 방문 기록 또한 없애준다.(폭파시켰기 때문) 폭파시키지 않아도 되면 방문했던 기록은 반영해주고 폭파시키지 않는다.
한번의 연쇄가 수행된 이후 뿌요가 내려오는 함수 drop()과 수행 문장은 다음과 같다.
def drop():
global field, visited
visited = [[0]*6 for _ in range(12)]
for i in range(1, 12):
for j in range(6):
if field[i][j] != '.' and field[i-1][j] == '.':
for k in range(i):
if field[k][j] == '.':
field[k][j] = field[i][j]
field[i][j] = '.'
break
while True:
array = []
for i in range(12):
for j in range(6):
if field[i][j] != '.' and not visited[i][j]:
q = deque([(i, j)])
t = bumb(field[i][j])
array.append(t)
if True in array:
ans += 1
drop()
if array == [] or not True in array:
break
print(ans)연쇄 수를 세는 과정이 조금 헷갈렸는데, 처음에는 bumb()가 한번 수행되고 나면 연쇄 수가 올라가는 줄 알고 그렇게 풀었다. 하지만 다시 문제를 자세히 읽어보니 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다. 이 조건 때문에 bumb()가 모두 수행되고 나서 한번의 연쇄를 추가시킨다.
구현은 처음부터 예상되는 반례나 알고리즘 흐름을 생각한 뒤 넘어가는게 키 포인트인것 같다ㅠ 주의해야지
