[백준/Python] 11559 Puyo Puyo

문제를 보고 어떻게 구현할 지 생각을 하며

1. 같은 색 뿌요가 모여있는 걸 확인

2. 그 뿌요들을 터뜨리기

3. 중력 역할을 하는 장치 만들기

1~3의 작은 세 부분으로 나눴는데 이 중 제일 어려웠던 건 3번..이었다

 

1번은 상하좌우 비교하다가 같으면 또 그 자리에서 상하좌우 비교하고, 하는 걸 반복해야하므로 BFS를 사용해야겠다고 생각했고,

2번은 해당하는 자리를 다 '.'로 바꾸면 되니까 크게 어렵지 않을 것이라고 생각했는데,

3번은 도저히 어떻게 해야할지 생각하기가 어려웠다. 중력의 영향을 받는 건 상하 방향인데, 처음 필드를 입력받을 때 좌우 방향으로 리스트를 만들어서 받으니까 어떻게 구현해야할지 막막했다

찾은 해결 방법은 gameMap[3][0]에서 한 칸 떨어지면 gameMap[4][0]으로 떨어진다. 즉 gameMap[i][j]에서 i를 1 증가시키면 한 칸 떨어뜨릴 수 있다는 것이다!!!!!!!

(자세한 풀이 방법은 아래에서!!)

from collections import deque

dx = [0, 0, 1, -1]  # 상하좌우
dy = [1, -1, 0, 0]  # 상하좌우

# 한 뿌요에서 인접한 곳에 같은 색의 뿌요가 있는지 확인하는 함수
def puyopuyo(i, j):
    q = deque()
    q.append((i, j))
    check.append((i, j))
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < 12 and 0 <= ny < 6 and gameMap[nx][ny] == gameMap[i][j] and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                q.append((nx, ny))
                check.append((nx, ny))

# 인접한 같은 색의 뿌요가 4개 이상이라면 터지게 하는 함수
def bang(check):
    for i, j in check:
        gameMap[i][j] = '.'

# 뿌요가 삭제되었을 떄 위에 있는 뿌요들이 내려오게 하는 함수
def drop():
    for y in range(6):
        for i in range(10, -1, -1):
            for j in range(11, i, -1):
                if gameMap[i][y] != '.' and gameMap[j][y] == '.':
                    gameMap[j][y] = gameMap[i][y]
                    gameMap[i][y] = '.'
                    break

gameMap = [list(input().rstrip()) for _ in range(12)]
times = 0
while True:
    flag = 0
    visited = [[0] * 6 for _ in range(12)]
    for i in range(12):
        for j in range(6):
            if gameMap[i][j] != '.' and visited[i][j] == 0:
                visited[i][j] = 1
                check = []
                puyopuyo(i, j)
                # 색깔이 같은 뿌요가 4개 이상이라면 터지도록
                if len(check) >= 4:
                    flag = 1
                    bang(check)

    if flag == 0:
        break
    drop()
    times += 1

print(times)

풀이과정

1. puyopuyo함수에 처음 만난 뿌요의 좌표를 넣고, 상하좌우에 같은 색의 뿌요가 있는지 확인

1-1. 있다면,  visited를 1로 바꾸고, check에 찾은 같은 색 뿌요의 좌표를 check라는 리스트에 append

1-2. 없다면, 함수를 나옴

 

2. check의 길이가 4 이상인(같은 색 뿌요가 4개 이상 인접해있는) 경우 bang 함수로

 

3. bang 함수에서는 받아온 check 리스트에 있는 좌표를 모두 '.'으로 바꿈 → 뿌요가 터진 것을 표현

 

4. bang 함수를 통해 뿌요를 터뜨렸다면, drop 함수를 통해 빈 칸으로 위에 있던 뿌요들이 떨어지도록 함

4-1. '.'이 뿌요보다 아래에 있다면 '.' 자리에 위에 있는 뿌요를 넣고, 위에 있던 뿌요 자리에 '.'를 넣음

4-2.  4-1을 반복하며 '.'이 뿌요보다 아래에 있는 경우가 없도록

4-3. drop 함수가 끝난 후, times를 += 1 해주어 연쇄가 몇 번 일어났는지 세도록 함

 

5. 1~4번을 반복하며 색깔이 같은 뿌요들을 터뜨리고 아래로 떨어지는 과정을 반복