백준 11559 [puyo puyo] 파이썬

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

 

예전에 재밌게하던 게임인데, 문제로 만나게되니 반가웠다.

 

이 문제의 핵심은

1) BFS로 탐색

2) 터지는 조건을 만족하게 되면, 터지는 것을 고려하여 나머지요소들을 움직인다

3) 안터질때까지 반복

#백준 11559 puyo puyo

from collections import deque
dr=[0,0,1,-1]
dc=[1,-1,0,0]
field=[]
for _ in range(12): #필드 초기화
    field.append(list(map(str,input())))

def bfs(color,start_row,start_col,visit,burst,is_burst):  # 컬러, 시작좌표(r,c), 방문배열, 터짐배열, 터졌는지 확인 플래그
    q=deque()
    q.append((start_row,start_col))
    temp_cnt=1
    temp_pos=deque()
    temp_pos.append((start_row,start_col))
    while q: #bfs로 탐색
        r,c=q.popleft()
        for i in range(4):
            R=r+dr[i]
            C=c+dc[i]
            if 0<=R<12 and 0<=C<6 and field[R][C]==color and visit[R][C]==0: #방문하지 않았다면 방문
                visit[R][C]=1
                temp_cnt+=1
                temp_pos.append((R,C))
                q.append((R,C))
    if temp_cnt>=4: #터졌다면 터짐배열 값 갱신 및 터짐확인 플래그 갱신
        for pos in temp_pos:
            burst[pos[0]][pos[1]]=1
        is_burst=True
    return visit,burst,is_burst

ans=0
while True:
    burst_flg=False
    visited=[[0 for _ in range(6)] for _ in range(12)]
    bursted=[[0 for _ in range(6)] for _ in range(12)]
    for i in range(12):
        for j in range(6):
            if visited[i][j]==0 and field[i][j]!='.':
                visited[i][j]=1
                visited,bursted,is_bursted=bfs(field[i][j],i,j,visited,bursted,False)
                burst_flg=(burst_flg | is_bursted)
    
    if burst_flg: #터졌다면 위치 이동
        for j in range(6):
            i=11
            temp=11
            while temp>-1 and i>-1:
                if bursted[temp][j]!=1:
                    field[i][j]=field[temp][j]
                    i-=1
                temp-=1
            while i>-1:
                field[i][j]='.'
                i-=1
        ans+=1
    else: #안터졌다면 종료
        break

print(ans)

정말 깔끔하게 정리한 GPT의 코드를 첨부한다.

큰 그림은 같다.

from collections import deque

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
field = [list(input().strip()) for _ in range(12)]

def bfs(r, c, color, visited):
    q = deque([(r, c)])
    cluster = [(r, c)]
    visited.add((r, c))
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dr[i], y + dc[i]
            if 0 <= nx < 12 and 0 <= ny < 6 and (nx, ny) not in visited and field[nx][ny] == color:
                visited.add((nx, ny))
                q.append((nx, ny))
                cluster.append((nx, ny))
    
    return cluster if len(cluster) >= 4 else []

def apply_gravity():
    for col in range(6):
        temp = [field[row][col] for row in range(12) if field[row][col] != '.']
        temp = ['.'] * (12 - len(temp)) + temp  # 위쪽을 '.'로 채우고 아래로 블록을 채움
        for row in range(12):
            field[row][col] = temp[row]

ans = 0
while True:
    visited = set()
    to_burst = []

    for i in range(12):
        for j in range(6):
            if field[i][j] != '.' and (i, j) not in visited:
                cluster = bfs(i, j, field[i][j], visited)
                if cluster:
                    to_burst.extend(cluster)

    if not to_burst:
        break

    for r, c in to_burst:
        field[r][c] = '.'

    apply_gravity()
    ans += 1

print(ans)