[BOJ] Python 백준 11559번 Puyo Puyo 골드 4

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

11559번: Puyo Puyo

문제 풀이

---

어렸을 때 많이 했던 뿌요뿌요(PuyoPuyo) 게임의 연쇄작용을 구현하는 문제이다.

 

테트리스와 비슷하지만 뿌요뿌요는 같은 색의 슬라임들이 4개 이상 연결되어있으면 터지고 빈 공간을 채운다는 점이 조금 다르다.

 

따라서 만약 테트리스였다면 행을 기준으로 탐색을 했겠지만 뿌요뿌요는 전체 탐색을 하면서 빈 공간이 아닐 때는 4개 이상 연결되었는지 BFS를 통해 체크하며 4개 이상인 모든 부분들을 빈 공간으로 치환하고 다시 바닥으로 정렬하는 과정을 반복해야 한다.

 

이때 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터지고 한 번의 연쇄가 추가된다고 하니 연쇄를 추가하는 부분을 정렬하는 과정에 위치시키면 적절할 것이다.

 

사실 12X6 크기의 행렬이라 상당히 크기가 작아 시간이나 공간에 대한 효율성을 따질 필요성까진 없지만 구현하는 과정에서 다소 헷갈리거나 복잡한 부분이 있었기에 문제를 세분화하여 주석을 통해 구현해야 할 기능들을 구분해놓고 구현하는 것이 도움 될 것 같다.

 

코드가 짧은 편은 아니라서 한눈에 들어오긴 힘들겠지만 한 줄씩 따라가다 보면 이해할 수 있을 것이다.

 

graph=[]
dir=[[-1,0],[1,0],[0,-1],[0,1]]
queue=[]
for i in range(12):
    graph.append(list(input()))
res=0

while True:
    check=True    #터졌는지 체크하는 변수
    visited=[[0 for i in range(6)]for j in range(12)]
    changed_col=[]
    del_queue=[]
    for i in range(12):
        for j in range(6):
            #뿌요가 존재하는 칸인 경우
            if graph[i][j]!="." and visited[i][j]==0:
                curr_char=graph[i][j]    #현재 뿌요 저장
                temp_cnt=0
                queue.append([i,j])
                visited[i][j]=1
                
                #현재뿌요와 연결되어있는 뿌요 탐색
                while len(queue)>0:
                    curr=queue.pop(0)
                    temp_cnt+=1
                    for k in range(len(dir)):
                        dy=dir[k][0]+curr[0]
                        dx=dir[k][1]+curr[1]
                        if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char and visited[dy][dx]==0:
                            queue.append([dy,dx])
                            visited[dy][dx]=1

                #연결된 뿌요가 4개 이상일 경우
                if temp_cnt>=4:
                    check=False
                    changed_col.append(j)
                    del_queue.append([i,j])
                    while len(del_queue)>0:
                        temp=del_queue.pop(0)
                        graph[i][j]="."
                        for k in range(len(dir)):
                            dy=dir[k][0]+temp[0]
                            dx=dir[k][1]+temp[1]
                            if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char:
                                del_queue.append([dy,dx])
                                graph[dy][dx]="."
                                if dx not in changed_col:
                                    changed_col.append(dx)

    if check:
        break
    else:
        res+=1
        #빈칸없게 위에 있는 뿌요들을 정렬
        for i in range(len(changed_col)):
            for j in range(10,-1,-1):
                if graph[j][changed_col[i]]!=".":
                    curr=j
                    while curr<=10 and graph[curr+1][changed_col[i]]==".":
                        graph[curr+1][changed_col[i]],graph[curr][changed_col[i]]=graph[curr][changed_col[i]],graph[curr+1][changed_col[i]]
                        curr+=1

print(res)

 

6번째 줄까지는 그래프를 입력받고 방향 리스트, 사용할 큐 초기화, 결과 변수를 선언했다.

 

8번째 줄의 while문은 더 이상 터진 뿌요들이 없을 때까지 터뜨리고 빈칸을 정렬하는 과정을 반복하는 부분이다.

 

check변수를 통해 터진 뿌요가 없을 경우 반복문을 탈출하고 매번 방문했는지 체크하는 visited 리스트를 초기화하도록 구현하였다.

 

13번째 줄부터는 전체 리스트를 반복하면서 뿌요가 존재할 경우 현재 뿌요를 저장하고 근접한 동일 뿌요들의 개수를 세서 4개 이상이라면 해당하는 뿌요들을 빈칸으로 초기화하였다.

 

이때 뿌요는 5종류가 있지만 변수에 현재 위치한 뿌요를 저장함으로써 종류에 대한 고려를 하지 않도록 했고 47번째 줄의 changed_col은 삭제된 뿌요가 존재하는 열을 추가하여 이후에 뿌요들을 정렬할 때 불필요한 탐색을 줄이는 방식으로 구현하였다.

 

53번째 줄에서 res+=1을 통해 카운트를 증가시키는데 문제에서 터질 수 있는 뿌요가 여러 그룹이라면 동시에 터지며 한 번의 연쇄가 추가되므로 다 터지고 난 뒤에 추가하도록 증가시키는 위치를 주의해야 한다.

 

터진 뿌요가 없다면 50번째 줄에서 반복문을 탈출하겠지만 터진 뿌요가 존재한다면 빈칸보다 위에 뿌요가 존재하지 않도록 정렬시킨 후 다시 반복문으로 돌아가면 된다.

 

그래프의 행을 기준으로 리스트 시작은 위, 끝은 바닥을 뜻하므로 끝부터 시작까지 역으로 오면서 뿌요를 최대한 리스트의 끝까지 정렬하는 것에 주의해야 한다.

 

해당 반복문이 끝나면 결과 변수인 res를 출력하면 끝이다.

 

결과 화면

 

그래프의 크기도 작고 특별한 알고리즘도 없이 흔한 그래프 이론으로 푸는 구현 문제였지만 구현 과정이 다소 길어지다 보니 충분히 헷갈릴 수도 있는 문제였다.

 

따라서 구현해야 하는 부분과 과정을 간략하게 주석으로 써놓고 차근차근 작성해 나가는 것이 실수를 방지하기 위해 중요한 것 같다.