BOJ 11559 - Puyo Puyo

BOJ 11559 - Puyo Puyo

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

뿌요뿌요는 먼저 중력의 영향을 받아 아래로 떨어지고, 이제 상하좌우로 같은 색 뿌요끼리 묶여있으면 같은 색 뿌요들이 없어진다고 합니다. 그리고 이것을 계속 반복한다고 하네요.

입력값을 살펴보니까 처음 입력값은 뿌요들이 전부 중력의 영향을 받아 아래로 떨어진 입력값만 주어진다고 합니다.

그러면 처음 작동을 중력이 아닌 뿌요를 먼저 터뜨리고, 그다음 중력을 적용하면 될 것 같습니다.

그래서 이번 코드는 총 3개로 나눠서 짜보겠습니다.

1. 입력값 받기

2. 뿌요 터뜨리기

3. 중력

1. 입력값 받기

12줄의 입력값을 받고, 한 줄에 6개의 입력값이 주어진다고 합니다. 그래서 n = 12, m = 6이라는 변수를 만들어주고, arr에 입력값을 저장해주면 됩니다. 그리고 몇 연쇄까지 나오는지 출력할 ans = 0도 선언합니다.

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

2. 뿌요 터뜨리기

이 문제는 같은 색끼리 연결하므로 플러드 필 알고리즘이 필요합니다. 저는 큐를 가지고 플러드 필을 만들 것이니 collections.deque를 불러오면 됩니다. 그리고 상하좌우로 인접한 칸들을 확인해야 하므로 dx, dy도 추가합니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

이제 (뿌요 터뜨리기) -> (중력) 과정을 더 터뜨릴 뿌요가 없을 때까지 돌려야 하므로 while 1이라는 무한 루프를 만들어주고, puyo_flag = False라는 bool 변수를 만들어줍니다. 이 변수는 뿌요가 터뜨리면 True로 바뀌고, 터뜨릴 뿌요가 없으면 조건문을 통해 while문을 탈출할 예정입니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False

그리고 for문으로 좌표들을 확인할 것인데, 플러드 필을 끝내고 다시 좌표들을 확인하다 보면 이미 방문한 좌표도 있을 것입니다. 그래서 arr과 크기가 같은 visit이라는 배열을 만듭니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0]*m for _ in range(n)]

visit[i][j] = 1이면 이미 방문한 노드이니 또 확인하지 않아도 된다는 뜻입니다.

이제 for문을 돌려서 각 좌표를 확인해주면 됩니다. 플러드 필을 돌릴 좌표는 visit[i][j] = 0이면서 arr[i][j] != '.'인 좌표입니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0 and arr[i][j] != '.':
                blah blah

(i, j)에서 플러드 필을 할 것이므로 visit[i][j] = 1로 바꿔줍니다. 그리고 큐를 만들어서 큐에 (i, j)를 넣어주고, while문을 통해 같은 색깔끼리 플러드 필을 해주면 됩니다. 뿌요를 터뜨려야하니 puyo = []라는 리스트로 하나 만들어줍니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0 and arr[i][j] != '.':
                visit[i][j] = 1
                q = deque([(i,j)])
                puyo = []

이제 while q를 통해 큐에서 원소를 뽑고, 인접한 칸 중에 arr[i][j]와 같은 색깔인 좌표들을 다시 넣으면서 반복하면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0 and arr[i][j] != '.':
                visit[i][j] = 1
                q = deque([(i,j)])
                puyo = [(i,j)]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x+dx[k], y+dy[k]
                        if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0 and arr[nx][ny] == arr[i][j]:
                            visit[nx][ny] = 1
                            q.append((nx,ny))
                            puyo.append((nx,ny))

이렇게 하면 이제 (i, j)에서의 플러드 필은 끝났습니다. 그러면 puyo 리스트에 저장된 좌표들이 있을 텐데, 뿌요뿌요는 같은 색 뿌요가 4개가 있어야지 터질 수 있으므로 len(puyo) >= 4일 때, arr[x][y] = '.'으로 바꿔주면 됩니다. 이때 뿌요가 터졌으므로 puyo_flag의 값을 True로 변경하면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0 and arr[i][j] != '.':
                visit[i][j] = 1
                q = deque([(i,j)])
                puyo = [(i,j)]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x+dx[k], y+dy[k]
                        if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0 and arr[nx][ny] == arr[i][j]:
                            visit[nx][ny] = 1
                            q.append((nx,ny))
                            puyo.append((nx,ny))
                if len(puyo) >= 4:
                    puyo_flag = True
                    for x,y in puyo:
                        arr[x][y] = '.'

이제 이 코드는 전체적으로 좌표를 훑어보면서 플러드 필을 하고, 뿌요들을 터뜨릴 것입니다. 하지만 뿌요가 터지지 않았다면 여기서 종료해야 하므로 조건문을 만들어줍니다. 뿌요가 터졌다면 ans += 1을 해주면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0 and arr[i][j] != '.':
                visit[i][j] = 1
                q = deque([(i,j)])
                puyo = [(i,j)]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x+dx[k], y+dy[k]
                        if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0 and arr[nx][ny] == arr[i][j]:
                            visit[nx][ny] = 1
                            q.append((nx,ny))
                            puyo.append((nx,ny))
                if len(puyo) >= 4:
                    puyo_flag = True
                    for x,y in puyo:
                        arr[x][y] = '.'
    if puyo_flag == True: ans += 1
    else: break

3. 중력 적용하기

중력을 적용하는 코드는 https://kau-algorithm.tistory.com/168 여기에서 설명한 적이 있으니 생략하겠습니다. 3번 문제 gravity를 확인하면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0 and arr[i][j] != '.':
                visit[i][j] = 1
                q = deque([(i,j)])
                puyo = [(i,j)]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x+dx[k], y+dy[k]
                        if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0 and arr[nx][ny] == arr[i][j]:
                            visit[nx][ny] = 1
                            q.append((nx,ny))
                            puyo.append((nx,ny))
                if len(puyo) >= 4:
                    puyo_flag = True
                    for x,y in puyo:
                        arr[x][y] = '.'
    if puyo_flag == True: ans += 1
    else: break
    
    for i in range(n-1):
        for x in range(n-1):
            for y in range(m):
                if arr[x][y] != '.' and arr[x+1][y] == '.':
                    arr[x][y], arr[x+1][y] = '.', arr[x][y]

그리고 이제 ans를 출력하면 됩니다.

from collections import deque
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

n, m = 12, 6
arr = list(list(input()) for _ in range(n))
ans = 0

while 1:
    puyo_flag = False
    visit = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0 and arr[i][j] != '.':
                visit[i][j] = 1
                q = deque([(i, j)])
                puyo = [(i, j)]
                while q:
                    x, y = q.popleft()
                    for k in range(4):
                        nx, ny = x + dx[k], y + dy[k]
                        if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0 and arr[nx][ny] == arr[i][j]:
                            visit[nx][ny] = 1
                            q.append((nx, ny))
                            puyo.append((nx, ny))
                if len(puyo) >= 4:
                    puyo_flag = True
                    for x, y in puyo:
                        arr[x][y] = '.'
    if puyo_flag == True:ans += 1
    else:break

    for i in range(n - 1):
        for x in range(n - 1):
            for y in range(m):
                if arr[x][y] != '.' and arr[x + 1][y] == '.':
                    arr[x][y], arr[x + 1][y] = '.', arr[x][y]
print(ans)