백준 16768번 <Mooyo Mooyo>

백준 알고리즘 16768번

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

16768번: Mooyo Mooyo

---

16768번

입력으로 첫 줄에 board의 행 수 N이 들어오고 연결된 블록의 수 K가 들어온다.

그 다음 N개의 줄에 걸쳐 board의 상태가 들어온다.

 

출력으로는 MooyoMooyo 게임을 모두 진행된 board의 상태를 출력한다.

---

문제 해결

뿌요뿌요와 비슷한 게임이다.

 

1. board에서 한 숫자가 K개 이상 인접해있으면 0으로 바꾼다.

2. board에서 0이 아닌 숫자 밑에 0이 있다면 그 0을 없애고 해당 숫자를 밑으로 내린다.

 

1번은 bfs함수와 zero함수를 이용하여 구현하였고

2번은 down 함수를 이용하여 구현하였다.

 

bfs(i, j, chk, N, K)

- bfs 알고리즘을 이용하여 (i, j) 좌표와 인접하고 chk의 값과 Map[i][j]의 값이 같은 좌표들을 coordinate에 저장하였다.

- set(coordinate)의 길이가 K보다 같거나 크다면 zero(coordinata) 함수를 호출한다.

- i, j 좌표는 처음에 coordinate에 저장되지 않지만 인접 좌표들의 인접 좌표로 되서 들어가게 된다.

 

zero(coordinate)

- coordinate에 저장되어 있는 좌표의 Map 값을 0으로 바꾸고 visit 값을 True로 바꾼다.

 

down()

- 0이 아닌 숫자 밑에 0이 없도록 해당 숫자를 밑으로 내린다.

- 이때 idx를 이용하여 0인 경우에는 0인 경우는 continue, idx와 for문의 i값과 같다면 idx에서 1을 빼고 i, j 좌표의 newMap의 값에 i, j 좌표의 Map의 값을 가져온다. 이 2가지 경우가 아닌 경우에는 idx, j 좌표의 newMap의 값에 i, j 좌표의 Map의 값을 가져오고 idx에서 1을 뺀다.

- 게임이 끝나는 경우를 알기 위해 check 변수를 이용하여 board 상태가 변하는 경우(False)와 변하지 않는 경우(True)를 구분한다.

 

visit 배열을 이용하여 Map에서 방문한 좌표를 저장해둔다.

Map이 게임이 진행되면서 바뀌기 때문에 visited 함수를 이용하여 Map에 대한 visit 배열을 update 한다.

---

코드

from collections import deque

N, K = map(int, input().split())
Map = [[0 for _ in range(10)] for _ in range(N)]
visit = [[False for _ in range(10)] for _ in range(N)]

for i in range(N):
    temp = input()
    for j in range(10):
        Map[i][j] = int(temp[j])
        if Map[i][j] == 0:
            visit[i][j] = True

def visited():
    for i in range(N):
        for j in range(10):
            if Map[i][j] == 0:
                visit[i][j] = True
            else:
                visit[i][j] = False

def zero(coordinate):
    for a, b in coordinate:
        Map[a][b] = 0
        visit[a][b] = True

def bfs(i, j, chk, N, K):
    di = [1, -1, 0, 0]
    dj = [0, 0, 1, -1]
    q = deque([(i, j)])
    coordinate = []
    while q:
        mi, mj = q.popleft()
        for k in range(4):
            newI = mi + di[k]
            newJ = mj + dj[k]
            if newI >= N or newJ >= 10 or newI < 0 or newJ < 0:
                continue
            if not visit[newI][newJ] and Map[newI][newJ] == chk:
                q.append((newI, newJ))
                coordinate.append((newI, newJ))
                visit[newI][newJ] = True
    if len(set(coordinate)) >= K:
        zero(coordinate)
def down(N):
    check = True
    newMap = [[0 for _ in range(10)] for _ in range(N)]
    for j in range(10):
        idx = N-1
        for i in range(N-1, -1, -1):
            if Map[i][j] == 0:
                continue
            if idx == i:
                idx -= 1
                newMap[i][j] = Map[i][j]
                continue
            check = False
            newMap[idx][j] = Map[i][j]
            idx -= 1
    if check:
        return Map, check  
    return newMap, check

        
while True:
    for i in range(N):
        for j in range(10):
            if visit[i][j]:
                continue
            chk = Map[i][j]
            bfs(i, j, chk, N, K)
    Map, check = down(N)
    if check:
        break
    visited()
            
for i in range(N):
    for j in range(10):
        print(Map[i][j], end="")
    print("")

---

결과

---