파이썬 백준 11559: Puyo Puyo

문제

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

 

 

 

풀이

1. 자료구조 결정

처음에 이차원리스트를 사용해야겠다고 생각했다. 구현중 뿌요가 내려올때 앞,뒤 모두에서 원소 빼고 넣을수 있게 리스트 안에 deque형태로 변경했다.

뿌요는 아래로 떨어지는데 열단위 변경보다 행단위변경이 쉬울거라 생각해서 입력받은 리스트를 전치했다. (잘못된 생각이였던듯.........)

[deque(['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'R', 'R']), deque(['.', '.', '.', '.', '.', '.', '.', '.', 'Y', 'Y', 'R', 'R']), deque(['.', '.', '.', '.', '.', '.', '.', '.', '.', 'G', 'Y', 'Y']), deque(['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'G', 'G']), deque(['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'G']), deque(['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'])]

 

2. 알고리즘 결정

뿌요가 4개 이상 모이면 터진다는 것에서 이전에 풀었던 단지번호매기기 문제가 생각났다.

https://pleasestudy-alswldi.tistory.com/119

파이썬 백준 2667번 : 단지번호붙이기

DFS로 구현했다. 

 

import sys
from collections import deque
import copy
sys.setrecursionlimit(100000000)

def DFS(x,y,color):
    if x<=-1 or x>=6 or y<=-1 or y>=12:
        return False
    if Graph2[x][y]==color:
        global result
        result+=1
        Graph2[x][y]='.' #탐색하면서 방문했다는 표시. 색깔알파벳이였던 뿌요를.으로 변경한다.
        DFS(x-1,y,color)
        DFS(x,y-1,color)
        DFS(x+1,y,color)
        DFS(x,y+1,color)
        return True
    return False


def boom(): #뿌요가 터진 후 밑으로 내리기위한 코드
    global Graph2
    GG=[]
    for i in range(6):
        GGG=deque([])
        for j in range(12):
            if Graph2[i][j]=='.': 
                continue
            else:
                GGG.append(Graph2[i][j])
        for k in range(12-len(GGG)):
            GGG.appendleft('.')
        GG.append(GGG)
    Graph2=GG

result=0
Graph=[]
is_boom=False
for _ in range(12):
    temp=list(sys.stdin.readline().strip())
    Graph.append(temp)
Graph2=[deque(t) for t in zip(*Graph)]
queue=[]
print(Graph2)

answer=0
while(True):
    for i in range(6):
        for j in range(12):
            temp_Graph= copy.deepcopy(Graph2)#연결요소의 개수가 4이하이면 이전에 복사해논 걸 사용
            if Graph2[i][j]!='.' and DFS(i,j, Graph2[i][j])==True : #처음 방문
                if result>=4:#연결요소의 개수가 4이상이면 .으로 바꾼걸 놔둔다.
                    is_boom=True
                else: # 4이상이 아니라면 위에서 copy했던(탐색되었던 것이 .으로 바뀌기 이전) Graph로 바꾼다
                    Graph2=temp_Graph
                result=0
    if is_boom==False:
        break
    answer+=1
    boom() #뿌요를 밑으로 내린다
    is_boom=False

print(answer)

 

 

 

반례)

아래와 같은 경우 뿌요가 내려가지 않으므로 1이 출력되어야한다!

#ans 1
......
......
......
......
......
......
......
......
......
......
RRRYYY
RRRYYY

 

터지고 난뒤 뿌요가 공중에 뜨지 않는지 확인하자. 

#ans=3
......
......
......
......
......
......
.G....
RR....
RY....
RYG...
RRY...
RYYGG.

 

 

 

덧) 당분간 뿌요뿌요는 안할듯..😣