AndroidTeacher

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

어렸을 때 해봤던 '뿌요뿌요' 게임을 구현한다고 생각하면 될 것 같다.

코드의 풀이 방식은 다음과 같다.

1. 맵(graph)을 돌면서 '.'이 아닌 것(뿌요)을 발견하면 BFS를 실행한다.

2. BFS로 진입하여 현재 터뜨릴 수 있는 뿌요를 모두 터뜨려 준다.

3. 뿌요가 터졌기 때문에 맵을 한번 정리해준다(gravity)

4. 터뜨릴 수 있는 뿌요가 계속 남아있을 때 까지 위 과정을 반복한다.

다만 주의 할 점은!

문제에도 명시되어 있지만 동시에 두 종류 이상의 뿌요가 터져도 한번의 연쇄만 추가 해야 한다는 것이다.

해당 설명은 코드 아래에도 다시 명시해 놓았다.

from collections import deque

graph = []

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

result = 0


def bfs(a, b, c):
    queue = deque()
    queue.append((a, b))

    pang = deque()
    pang.append((a, b))

    visited = [[False] * 6 for _ in range(12)]
    visited[a][b] = True
    count = 1
    flag = 0

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > 11 or ny < 0 or ny > 5:
                continue
            if graph[nx][ny] == c and not visited[nx][ny]:
                queue.append((nx, ny))
                pang.append((nx, ny))
                visited[nx][ny] = True
                count += 1

    if count >= 4:
        flag = 1

        for x, y in pang:
            graph[x][y] = "."

    return flag


def gravity():
    for y in range(6):
        queue = deque()
        for x in range(11, -1, -1):
            if graph[x][y] != '.':
                queue.append(graph[x][y])
        for x in range(11, -1, -1):
            if queue:
                graph[x][y] = queue.popleft()
            else:
                graph[x][y] = '.'


for i in range(12):
    graph.append(list(input()))


while True:
    chk = 0
    for i in range(12):
        for j in range(6):
            if graph[i][j] != '.':
                chk += bfs(i, j, graph[i][j])

    if chk == 0:
        print(result)
        break
    else:
        result += 1
    gravity()

# 처음에는 result를 bfs함수 안에서 global 변수로 선언하여
# 팡이 될 때 마다 +1을 해주는 방식으로 하였는데
# 이렇게 해주면, 동시에 두 뿌요가 터지는 경우에도 두 개를 카운트를 해 준다.
# 하지만 문제에서, 동시에 여러개의 뿌요가 터질 때는 한 번 카운트를 해주라고 명시했기 때문에
# bfs 함수 안이 아닌, 바깥에서 +1을 해주는 방식으로 변경하였다. 이렇게 하니 정답이 나온다.

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !