BOJ 11559 - Puyo Puyo

BOJ 11559 - Puyo Puyo

๋ฟŒ์š”๋ฟŒ์š”๋Š” ๋จผ์ € ์ค‘๋ ฅ์˜ ์˜ํ–ฅ์„ ๋ฐ›์•„ ์•„๋ž˜๋กœ ๋–จ์–ด์ง€๊ณ , ์ด์ œ ์ƒํ•˜์ขŒ์šฐ๋กœ ๊ฐ™์€ ์ƒ‰ ๋ฟŒ์š”๋ผ๋ฆฌ ๋ฌถ์—ฌ์žˆ์œผ๋ฉด ๊ฐ™์€ ์ƒ‰ ๋ฟŒ์š”๋“ค์ด ์—†์–ด์ง„๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด๊ฒƒ์„ ๊ณ„์† ๋ฐ˜๋ณตํ•œ๋‹ค๊ณ  ํ•˜๋„ค์š”.

์ž…๋ ฅ๊ฐ’์„ ์‚ดํŽด๋ณด๋‹ˆ๊นŒ ์ฒ˜์Œ ์ž…๋ ฅ๊ฐ’์€ ๋ฟŒ์š”๋“ค์ด ์ „๋ถ€ ์ค‘๋ ฅ์˜ ์˜ํ–ฅ์„ ๋ฐ›์•„ ์•„๋ž˜๋กœ ๋–จ์–ด์ง„ ์ž…๋ ฅ๊ฐ’๋งŒ ์ฃผ์–ด์ง„๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋Ÿฌ๋ฉด ์ฒ˜์Œ ์ž‘๋™์„ ์ค‘๋ ฅ์ด ์•„๋‹Œ ๋ฟŒ์š”๋ฅผ ๋จผ์ € ํ„ฐ๋œจ๋ฆฌ๊ณ , ๊ทธ๋‹ค์Œ ์ค‘๋ ฅ์„ ์ ์šฉํ•˜๋ฉด ๋  ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

๊ทธ๋ž˜์„œ ์ด๋ฒˆ ์ฝ”๋“œ๋Š” ์ด 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)

Last updated