[백준_11559]Puyo Puyo with Python

백준(BOJ) 시뮬레이션: Puyo Puyo(골드 5)

문제 출처: https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

 

1. 알고리즘

• while 반복문으로 더 이상 뿌요가 터지지 않을 때까지 반복
• puyo_field의 모든 칸을 확인하여 뿌요가 뭉쳐있는 그룹을 확인
  • 칸 탐색 시 방문 이력을 표시하기 위해 visited 리스트를 공유하여 사용
  • 각 칸이 '.'이면 탐색하지 않고 넘어감
  • find_puyo_group 함수로, 각 칸의 색과 동일한 뿌요와 뭉쳐있는 뿌요 좌표 리스트를 구함.
    • BFS 알고리즘으로 탐색
    • 탐색할 좌표의 뿌요 색이 기준 뿌요 색과 일치할 경우
      • 탐색 좌표 추가, 방문 처리, 뿌요 그룹 리스트에 좌표 추가
    • 뿌요 그룹 리스트가 존재할 경우, 기준 뿌요 좌표를 추가하여 반환
    • 뿌요 그룹 리스트가 존재하지 않을 경우, None Type 반환
  • 뿌요 그룹 리스트가 존재하고, 뭉쳐있는 뿌요가 4개 이상이면 삭제할 뿌요 리스트에 추가
• 삭제할 뿌요 리스트가 존재할 경우
  • 뿌요를 삭제하고, 밑으로 내려주는 erase_and_move_puyo_group함수를 사용, 이동 후 그래프를 반환 받음
  • 연쇄 횟수 + 1
• 삭제할 뿌요 리스트가 존재하지 않는 경우
  • 연쇄가 끝났으므로, 지금까지의 연쇄 횟수를 출력하고 while문 break

 

2. 유의사항

• 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야함.
  • 여러 그룹이 터져도 동시에 터진 것이기 때문에 연쇄 횟수 + 1

 

3. 어려웠던 점, 해결방안

 

4. 소스코드

상세 코드 설명은 주석

import sys
from collections import deque
 
#뭉쳐져 있는 뿌요 그룹 찾는 함수(BFS)
def find_puyo_group(start, puyo_color, graph):
    route = deque([start])
 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    #뿌요 그룹 리스트
    puyo_group_list = []
    while route:
        x, y = route.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
 
            #범위 밖일 경우 pass
            if not 0<=nx<12 or not 0<=ny<6:
                continue
 
            #탐색 중인 칸의 뿌요 색이 현재 탐색기준 뿌요 색과 동일하고, 방문한 적이 없을 때
            if graph[nx][ny] == puyo_color and visited[nx][ny] == 0:
                #다음 탐색 대상 좌표 추가, 방문 처리
                route.append((nx, ny))
                visited[nx][ny] = 1
                #뿌요 그룹 리스트에 추가
                puyo_group_list.append((nx, ny))
 
    #뿌요 그룹 리스트 존재 시
    if puyo_group_list:
        #탐색기준 뿌요 위치(시작 위치)를 그룹 리스트에 추가, 반환
        puyo_group_list.append(start)
        return puyo_group_list
    #뿌요 그룹 리스트가 존재하지 않을 때, None 반환
    else:
        return None
 
 
#뿌요 그룹을 삭제하고, 뿌요들을 내려주는 함수
def erase_and_move_puyo_group(erase_list, graph):
    #삭제 뿌요 리스트에 따라 뿌요 삭제
    for x, y in erase_list:
        graph[x][y] = '.'
    
    #뿌요 필드 전치(열 연산을 행 연산으로 더 간단하게 하기 위함)
    _graph = list(map(list, zip(*graph)))
    for idx in range(6):
        #빈 공간 갯수 만큼 비어있는('.'으로 차 있는) 리스트 생성
        empty_line = ['.'] * _graph[idx].count('.')
        #빈 공간 뒤에 뿌요리스트 추가
        _graph[idx] = empty_line + [puyo for puyo in _graph[idx] if puyo != '.']
    #다시 원래의 형태로 전치
    graph = list(map(list, zip(*_graph)))
 
    return graph
 
 
input = sys.stdin.readline
if __name__ == '__main__':
    puyo_field = [list(*map(list, input().split())) for _ in range(12)]
 
    temp_field = [r[:] for r in puyo_field]
    count = 0
    while True:
        erase_puyo_list = []
        visited = [[0] * 6 for _ in range(12)]
        for r in range(12):
            for c in range(6):
                #칸이 '.'로 뿌요가 없을 시 pass
                if temp_field[r][c] == '.':
                    continue
                
                #시작 칸 방문 처리
                visited[r][c] = 1
                #뭉쳐있는 뿌요 그룹 찾기
                puyo_group = find_puyo_group((r, c), temp_field[r][c], temp_field)
                #뭉쳐져 있고, 뭉쳐진 뿌요가 4개 이상이면 삭제 뿌요 리스트에 추가
                if puyo_group and len(puyo_group) >= 4:
                    erase_puyo_list.extend(puyo_group)
        
        #삭제할 뿌요가 있을 때
        if erase_puyo_list:
            #뿌요 삭제 후 이동 함수를 통해 처리 후의 뿌요 필드를 반환받음
            temp_field = erase_and_move_puyo_group(erase_puyo_list, temp_field)
            #연쇄 횟수 1회 추가
            count += 1
        #삭제할 뿌요가 없을 때 == 연쇄가 끝났을 때
        else:
            #연쇄 횟수 출력 후 반복문 종료
            print(count)
            break
 

 

5. 고민