[골드 IV] 11559번. Puyo Puyo

 문제 

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

11559번: Puyo Puyo

 사용 언어 

Python3

 풀이 과정 

 골드 IV  문제 내 힘으로 풀어보겠다고 6시간을 쓴 날에 대하여...🤦‍♀️

 

여느 때처럼 문제 설명은 짧고 명료했다. 어떻게 구현해야 할지 느낌도 왔다! 그런데 막상 처음 제출까지 (설렁 설렁 풀며 딴 짓도 좀 했지만) 3시간 정도 걸린 것 같고... 18% 쯤에서 틀렸습니다가 떠서 다시 고치는 데 3시간은 걸린 것 같다 ㅋ

시간을 계속 쓰는 게 아깝기도 했지만 진짜 진짜 쫌만 하면 풀릴 것 같고 오늘은 자소서 쓸 곳도 없겠다 해서 마지막엔 야식도 챙겨 먹고 집중했다.

 

처음 내가 뿌요를 떨어뜨리려고 구현한 문제의 코드이다.

if count >= 4:
        # 뿌요가 한 번이라도 터지면 콤보!
        trigger = True
        # 뿌요를 터뜨리는 함수 돌리기
        puyo_cnt = Counter([y for x, y in puyo])
        for px, py in puyo:
            if px - puyo_cnt[py] < 0:
                state[px][py] = "." 
            else:
                state[px][py] = state[px - puyo_cnt[py]][py]
                state[px - puyo_cnt[py]][py] = "."

 

당연히 예제 문제는 답이 잘 나오기 때문에 왜 틀렸는지 감도 못잡고 질문하기에서 추천해주는 예제를 다 집어넣어봤다. 3개쯤 돌렸을 때 문제가 되는 엣지케이스를 찾을 수 있었는데... 다음의 경우이다.

 

저렇게 한 줄에 몇 개의 뿌요가 터지는지만 확인하고 내리면 사라지는 뿌요가 붙어있지 않을 경우 이렇게 공중에 떠 있는 뿌요들이 생기는 것이었다. 그래서 결론은 제일 고심하며 구현했던 저 부분을 다 뜯어고쳐야 하는 것이었고... 과부화 와서 좀 쉬다가 다시 보니 세로로 한 줄씩 접근해야 할 것 같았다. 그런데 거꾸로 접근하는 방법도 헷갈려서 헤매다가 그냥 이중 for문의 안과 밖을 바꿔주면 되는 문제였다는 걸 깨달았고 한 줄에 남아있는 뿌요끼리 모아서 쌓아주기 위해 deque를 사용했다.

 

제출했더니 맞았습니다!! 👏👏👏👏👏 박수 👏👏👏👏👏

시간도 오래 걸릴까봐 걱정했는데 적어서 마음에 들지만 예상과 다르다니. 아무래도 시간 복잡도 계산하는 방법을 좀 날 잡고 정리해야겠다.

 

 제출 답안 

from collections import deque
from sys import stdin
input = stdin.readline

# 4개 이상의 뿌요가 모이면 터진다!
# 여러 그룹이 있으면 동시에 터지고 이후 상황에서 터지면 콤보가 쌓인다!
def PuyoPop(i, j):
    global trigger
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    count = 1
    puyo = [(i, j)]
    q = deque([(i, j)])
    visited[i][j] = True
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < 12 and 0 <= ny < 6 and visited[nx][ny] == False:
                # 상하좌우의 같은 색 뿌요 찾기
                if state[x][y] == state[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))
                    count += 1
                    puyo.append((nx, ny))
    
    if count >= 4:
        # 뿌요가 한 번이라도 터지면 콤보!
        trigger = True
        # 뿌요를 터뜨리는 함수 돌리기
        for px, py in puyo:
            state[px][py] = "."


# 중력에 의해 떨어지는 뿌요!
def PuyoDrop(state):
    for j in range(6):
        q = deque([])
        for i in range(11, -1, -1):
            # 한 줄에 남아있는 뿌요들만 모으기
            if state[i][j] != '.':
                q.append(state[i][j])
        # 바닥부터 차례로 채워주고 남는 공간은 .으로 채우기
        for i in range(11, -1, -1):
            if q:
                state[i][j] = q.popleft()
            else:
                state[i][j] = "."


state = [list(input().strip()) for _ in range(12)]
trigger = True

if __name__ == "__main__":
    combo = 0
    while trigger == True:
        trigger = False
        visited = [[False] * 6  for _ in range(12)]
        for i in range(11, -1, -1):
            for j in range(6):
                if visited[i][j] == False and state[i][j] != ".":
                    # 현재 상황에서 터뜨리기 가능한 뿌요들 팡
                    PuyoPop(i, j)

        # 한 번이라도 터졌으면 콤보 올리고 빈 칸 채우기 
        if trigger == True:
            combo += 1
            PuyoDrop(state)

    print(combo)

 

 공부한 내용 

이중 for문 세로로 한 줄씩 접근하기

분명히 for문으로도 가능할텐데,  이 부분을 구현하려고 하면서 머리가 안 돌아가서 그냥 가로 세로 반대로인 배열을 하나 더 만들어서 대입할까 고민했다.... 그런데 그럴 필요가 전혀 없다는 것!!! 쫌만 생각하면 기존의 배열에서 인덱스만으로도 편하게 접근할 수 있다.

 

아래와 같이 12 * 6 구조의 리스트가 있으면 평소에는 오른쪽과 같이 접근했다.

for i in range(11, -1, -1):
    for j in range(6):
        if visited[i][j] == False and state[i][j] != ".":
            # 현재 상황에서 터뜨리기 가능한 뿌요들 팡
            PuyoPop(i, j)

 

그런데 반대로 "..........RR" "........YYRR"과 같이 접근하고 싶으면 그냥 인덱스를 반대로 바꿔주면 된다.

for j in range(6):
    q = deque([])
    for i in range(11, -1, -1):
        # 한 줄에 남아있는 뿌요들만 모으기
        if state[i][j] != '.':
            q.append(state[i][j])
    # 바닥부터 차례로 채워주고 남는 공간은 .으로 채우기
    for i in range(11, -1, -1):
        if q:
            state[i][j] = q.popleft()
        else:
            state[i][j] = "."

 

정리를 하고 보니 이걸 고민했다가 풀었다고 정리한 게 웃긴데 나중에 까먹지 않기 위해... 작성한다.

 

 다른 사람 코드 

1. 

a=[[*input()] for _ in range(12)]
di,dj=[0,1,0,-1],[1,0,-1,0]
def puyo():
  flag=1
  for i in range(12):
    for j in range(6):
      if a[i][j]!='.':
        dfs=[(i,j)]
        check=[(i,j)]
        while dfs:
          s,t=dfs.pop()
          for k in range(4):
            i1,j1=s+di[k],t+dj[k]
            if 0<=i1<12 and 0<=j1<6 and a[i1][j1]==a[s][t] and (i1,j1) not in check:
              dfs.append((i1,j1))
              check.append((i1,j1))
        if len(check)>=4:
          flag=0
          for s,t in check:
            a[s][t]='.'
  return flag
def fall():
  for j in range(6):
    c=''
    for i in range(11,-1,-1):
      if a[i][j]!='.':
        c+=a[i][j]
    for i in range(len(c)):
      a[11-i][j]=c[i]
    for i in range(12-len(c)):
      a[i][j]='.'
combo=0
while 1:
  if puyo(): print(combo); break
  fall()
  combo+=1

➡ 떨어지는 부분을 더 간단하게 구현한 것 같아서 가져와봤다. 나는 문자열을 그대로 사용하지 않고 리스트로 분리했기 때문에 위 방법은 사용하지 못했지만 문자열의 경우 이렇게 짤 수 있다는 걸 확인했다!