[백준] 11559 : Puyo Puyo (파이썬)

728x90

728x90

 

11559번: Puyo Puyo

 

누가 말했나, 매도 일찍 맞는 게 낫다고... 오랫동안 구현 문제를 피하다가 2주 전부터 구현 문제를 아주 많이 풀고 있다. 중급 알고리즘 스터디로 넘어오면서 이제 실전과 비슷한 난이도의 문제를 풀기 위해 구현 집어넣고 온갖 골드 문제를 풀어대고 있는데 이 뿌요 문제도 그 중 하나이다. 사실 예전에도 본 적은 있지만 이게.. 뭐야? (흐린눈) 하고 지나가서 시도조차 안 했던 문제다.

문제는 그래도 쉬운 편인 것 같다. Puyo Puyo 문제의 입력은 12 * 6으로 픽스되어 있어 완전탐색해도 딱히 부담없는 사이즈다. 그런데 진짜 문제는 동시에 터지는 것들을 각개로 계산하는 게 아니라 1콤보로 계산해야 한다는 점인데, 이건 저번에 푼 '인구이동' 문제에서 비슷한 작업을 해서 좀 수월하게 풀 수 있었다.

 

간단하다. 터지는 뿌요들의 위치를 저장하는 큰 리스트가 있으면 된다.

 

from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
location = []	# 이 리스트는 터져야 할 영역에 있는 것들이 중복 계산되지 않도록 관리
visited = [[0 for _ in range(6)] for _ in range(12)]
def bfs(color, x, y):
  qu = deque([[x, y]])
  delete = [[x, y]]	# 터질 뿌요들의 좌표들이 있음

  while qu:
    x, y = qu.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or nx >= 12 or ny < 0 or ny >= 6:
      # 뿌요 보드를 넘어가면 그냥 가기
        continue
      if field[nx][ny] != color or visited[nx][ny]:
      # 색깔이 다르거나 이미 방문한 좌표라면 그냥 가기
        continue
      visited[nx][ny] = 1
      qu.append([nx, ny])
      if [nx, ny] not in delete:
        delete.append([nx, ny])
  return [] if len(delete) < 4 else delete

field = [list(input()) for _ in range(12)]
d_row = 0
combo = 0
while True:
  d = []
  location = []
  visited = [[0 for _ in range(6)] for _ in range(12)]
  add = 0
  for i in range(d_row, 12):
    if field[i] == ['.', '.', '.', '.', '.', '.',]:
    # 만약 다 빈 줄이라면 앞으로도 빈 줄일 것이므로 d_row를 추가해 다음 순회에는 보지 않는다
      d_row += 1
      visited[i] = [1, 1, 1, 1, 1, 1]
      continue

    for j in range(6):
    # 만약 비었거나, 이미 방문했거나 삭제될 뿌요 위치에 있다면 그냥 간다
      if field[i][j] == '.' or visited[i][j] or [i, j] in location:
        continue
      color = field[i][j]
      visited[i][j] = 1
      # 터질 수 있는 뿌요인지 확인하기 위해 BFS 함수를 돌린다
      delete = bfs(color, i, j)
      # 만약 delete가 비었다면 주변에 터질 수 있는 뿌요가 없는 것이므로 그냥 간다
      if not delete:
        continue
      # 만약 delete가 있다면, 터질 수 있는 뿌요이므로 d라는 큰 리스트에 저장
      d.append(delete)
      # 중복으로 터지는 일이 없도록 location에도 해당 좌표들을 넣어준다
      location += delete
  
  # 만약 d가 비었다면 이번 판에 터질 뿌요들이 없는 것이므로 끝낸다
  if not d:
    break
  
  for delete in d:
    for x, y in delete:
    # 만약 뿌요 좌표가 맨윗줄이라면 빈 것으로 채운다
      if x == 0:
        field[x][y] = '.'
        continue
      # 뿌요가 비지 않고, x가 0보다 큰 동안 바로 윗줄을 아래로 끌어당긴다
      while field[x][y] != '.' and x > 0:
        field[x][y] = field[x-1][y]
        x -= 1
      field[0][y] = '.'

  combo += 1	# 콤보는 루프가 끝날 때 1번만 올려준다
print(combo)

 

풀이방법

(1) 12줄을 차례대로 돌되, .으로 전부 채워진 빈 줄은 앞으로도 다른 색깔로 채워질 일이 없으므로 다음 루프에서 볼 필요 없다는 표시를 해준다.

(2) 글자가 있다면(뿌요가 있다면) 터질 수 있는 뿌요인지 보기 위해 BFS를 돌기 시작한다. 같은 글자가 얼마나 붙어 있는지 세고 4개가 안 되면 버린다.
(3) 4개 이상이 된다고 해도 전체 필드를 다 보기 전까지는 터뜨리면 안 되므로 큰 리스트에 저장한다.
(4) 필드를 다 돌면 리스트에 있는 것들을 터뜨리기 시작함. 터뜨리는 건 위에 있는 걸 그냥 복사해서 원 위치에 있는 것을 없애버리는 것으로 대신한다. (대신, 0번 줄이 터지면 '.'으로 대체)
(5) 큰 리스트에 아무것도 없을 때까지 (1)~(4)번 반복한다.

 

다른 방법도 있을 텐데 나는 이렇게 풀었다.

뿌요가 터지는 건 결국 윗줄에 있는 게 그대로 내려온다는 의미이다. 그러므로 터질 뿌요 자리를 '.'으로 채웠다가 위의 것을 끌어내리는 것보다 그냥 위에 있는 걸 그대로 덮어쓰는 게 생각하기도 쉽다.

 

 

 

728x90

반응형

저작자표시비영리변경금지

'자료구조&알고리즘 > BOJ' 카테고리의 다른 글

[백준] 17406 : 배열 돌리기 4 (Python3)  (0)	2022.02.15
[백준] 11559 : Puyo Puyo (파이썬)  (0)	2022.02.12
[백준] 1806 : 부분합 (파이썬)  (0)	2022.02.11
[백준] 2504 : 괄호의 값 (파이썬)  (1)	2022.01.10
[백준] 1978 : 소수 찾기 (파이썬)  (1)	2021.09.07