https://www.acmicpc.net/problem/11559
-
문제
뿌요뿌요의 룰은 다음과 같다.
필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.
뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자! -
입력
총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.
이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.
R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다. -
출력
현재 주어진 상황에서 몇연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.
어려워보여서 풀기싫었다 사실..
원석오빠가 좋은문제라고 추천해줘서 풀어보았는데 역시 시간이 좀 많이 걸렸당 ㅠㅠ
그래도 어려운문제 중에 다른풀이 참고안하고 나혼자 푼 몇안되는 문제여서 뿌듯하군.. 근데 시간이 너무 오래걸려서 ㅠㅠ 시간줄이는 연습해야겠다이제!
일단 뿌요들을 폭파시키는 함수와 공백을 없애는 함수를 만들었다.
뿌요폭파함수는 DFS로 구현하였는데 그러다보니 ㅗ, ㅜ, ㅓ, ㅏ 를 구현하려면 2단계에서 현위치에서 재탐색해주어야 했다. BFS가 더 편할듯싶다. 어 그러면 테트로미노도 BFS가 더 편하려나..? 해봐야겠다
그리고 dfs에서 리턴하면 리턴값이 씹히는..? 것 때문에 시간이 엄청 오래걸렸다! 아무래도 재귀다보니까 당연한건데 그걸로 시간끌었당..
그리고 음 공백없애는 함수에서도 맨 아래 행부터 탐색해야되는 것을 깨닫는데에 오래걸려서 ..
이제 어려운 문제들도 차근차근 풀어봐야겠다
from collections import deque
def dfs(x, y, step): # 인접한 것들 터뜨리는 함수
global check
dx = [-1, 1, 0, 0] # 방향벡터
dy = [0, 0, -1, 1]
cnt = 0 # 터뜨릴지 확인하는 용도
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<12 and 0<=ny<6 and lst[x][y] == lst[nx][ny] and lst[x][y] != 'x' and visited[nx][ny] == 0:
# 범위안에 있고 방문되지않았고 같은 색깔인 경우(공백은 안침)
queue.append((nx, ny))
visited[nx][ny] = 1
dfs(nx, ny, step+1)
visited[nx][ny] = 0
if step == 2: # ㅓ, ㅏ, ㅗ, ㅜ 만들기위함!!!!!!!!!!!!!! 이것때문에 BFS가 편할 수 있을거같음 !!!!!!ㅠㅠㅠ
visited[nx][ny] = 1
dfs(x, y, step+1) # 탐색은 현위치에서 다시
visited[nx][ny] = 0
else:
cnt += 1 # 인접한것이 없으면 +1
if step >= 4 and cnt == 4: # 4개이상이고 더이상 인접한게 없으면
while queue: # 큐가 빌때까지
xx, yy = queue.popleft() # 터뜨릴좌표 꺼냄
lst[xx][yy] = 'x'
# print(step, xx, yy)
# print("y")
check = 1
def emp(): # 공백 비우는 함수
for i in range(11, -1, -1): # 꼭 밑에서부터 !!!
for j in range(5, -1, -1):
if lst[i][j] == 'x' and 0 < i: # 공백이고 맨윗줄이 아니면
n = 1
for k in range(i-1, -1, -1): # 위로 거슬러감
if lst[k][j] != 'x':
break
else:
n += 1 # 공백 세로 수
for k in range(i, -1, -1): # 공백 윗줄들
if k-n >= 0:
lst[k][j] = lst[k-n][j] # 공백만큼 아래로 끌어옴
else:
lst[k][j] = '.'
if lst[i][j] == 'x' and i == 0: # 공백이고 맨 윗줄이면
lst[i][j] = '.'
if __name__ == "__main__":
# lst = [list(input().split()) for i in range(12)] ------> 이렇게 하면 안됨!!!!
lst = [list(input()) for i in range(12)]
visited = [[0 for i in range(6)] for j in range(12)] # 방문체크
queue = deque() # 터뜨릴 좌표
check = 1
ans = 0
while check == 1: # 터지는게 있는동안만
check = 0
# print("start")
for i in range(12):
for j in range(6):
if lst[i][j] != '.':
visited[i][j] = 1 # 초기값도 방문 꼭꼭
queue.append((i, j)) # 터뜨릴 좌표 큐에 현위치 넣어줌
dfs(i, j, 1) # 리턴값
visited[i][j] = 0
queue.clear() # 다음턴을 위해 큐 초기화
# print("End, %d" % check)
if check == 1: # 전체 한번 돌았을때 터지는게 있다면
emp() # 공백 치우기
ans += 1 # 횟수늘리기
# print(lst)
# else:
# break
print(ans)