[Python/파이썬] - 백준(BOJ) 11559번 : Puyo Puyo

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

11559번: Puyo Puyo

 

주어진 조건에 맞게 구현하는 문제입니다.

 

같은 색깔이 4개 이상 확인 하는 코드를 Check 함수로 만들었고

Check한 원소들을 '.'으로 바꿔주는 코드를 Pop 함수로 만들었고

빈칸을 채우는 코드를 Gravity로 만들었습니다.

 

우선 Check 함수에서는 DFS로 탐색하며 같은 색깔의 원소를 q라는 배열에 담아둡니다.

이후 함수가 종료되면 q 배열을 Puyo라는 dict에 넣어서 색깔별, 인접해있는 원소끼리 분류해줍니다.

 

그리고 Pop 함수를 실행하여 Puyo를 for문으로 색깔별로 4개 이상 있으면 그 좌표의 원소를 '.'으로 바꿔줍니다

Pop을 한번도 하지 않는다면 종료를 시켜야 하기 때문에 종료 조건인 p를 return 해줍니다.

 

이후 Gravity 함수를 실행하여 아래에서부터 '.'을 체크하고 가장 가까운 같은 열의 원소와 바꿔줍니다.

만약 맨 위까지 탐색했는데 '.'만 있는 경우 윗칸에 있는원소를 탐색하지 않아도 되기 때문에 0을 return 해줍니다.

 

이 사이클을 Pop이 더이상 되지 않을때까지 반복한 후 반복한 회수를 print 해줍니다.

 

 

코드 :

def Check(y, x, q):
    visit[y][x] = 1
    q.append([y, x])
    for i in range(4):
        yy = y + dy[i]
        xx = x + dx[i]
        if 0 <= yy < 12 and 0 <= xx < 6 and visit[yy][xx] == 0 and arr[yy][xx] == arr[y][x]:
            Check(yy, xx, q)

def Pop():
    p = 0
    for i in Puyo:
        for j in Puyo[i]:
            if len(j) < 4:
                continue
            for yy, xx in j:
                arr[yy][xx] = '.'
            p = 1
        Puyo[i] = []
    return p

def Gravity(y, x):
    for yy in range(y-1, -1, -1):
        if arr[yy][x] != '.':
            arr[y][x] = arr[yy][x]
            arr[yy][x] = '.'
            return 1
    return 0

arr = [list(map(str,input())) for _ in range(12)]
Puyo = {'R' : [], 'G' : [], 'B' : [], 'P' : [], 'Y' : []}

dy = [0,1,0,-1]
dx = [1,0,-1,0]
answer = 0
while True:
    visit = [[0 for _ in range(6)] for _ in range(12)]
    for j in range(6):
        for i in range(11, -1, -1):
            if arr[i][j] == '.':
                break
            if visit[i][j] == 0:
                temp = []
                Check(i, j, temp)
                Puyo[arr[i][j]].append(temp)
    if not Pop():
        break
    answer += 1
    for j in range(6):
        for i in range(11, -1, -1):
            if arr[i][j] == '.':
                if not Gravity(i, j):
                    break
print(answer)