BOJ 11559 - Puyo Puyo
BOJ 11559 - Puyo Puyo
๋ฟ์๋ฟ์๋ ๋จผ์ ์ค๋ ฅ์ ์ํฅ์ ๋ฐ์ ์๋๋ก ๋จ์ด์ง๊ณ , ์ด์ ์ํ์ข์ฐ๋ก ๊ฐ์ ์ ๋ฟ์๋ผ๋ฆฌ ๋ฌถ์ฌ์์ผ๋ฉด ๊ฐ์ ์ ๋ฟ์๋ค์ด ์์ด์ง๋ค๊ณ ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๊ฒ์ ๊ณ์ ๋ฐ๋ณตํ๋ค๊ณ ํ๋ค์.
์ ๋ ฅ๊ฐ์ ์ดํด๋ณด๋๊น ์ฒ์ ์ ๋ ฅ๊ฐ์ ๋ฟ์๋ค์ด ์ ๋ถ ์ค๋ ฅ์ ์ํฅ์ ๋ฐ์ ์๋๋ก ๋จ์ด์ง ์ ๋ ฅ๊ฐ๋ง ์ฃผ์ด์ง๋ค๊ณ ํฉ๋๋ค.
๊ทธ๋ฌ๋ฉด ์ฒ์ ์๋์ ์ค๋ ฅ์ด ์๋ ๋ฟ์๋ฅผ ๋จผ์ ํฐ๋จ๋ฆฌ๊ณ , ๊ทธ๋ค์ ์ค๋ ฅ์ ์ ์ฉํ๋ฉด ๋ ๊ฒ ๊ฐ์ต๋๋ค.
๊ทธ๋์ ์ด๋ฒ ์ฝ๋๋ ์ด 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