이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 28 번째 글 입니다.
목차
골드5 : 구현 문제이다.
풀이
구현에 쪼는 줄 알았는데 생각보다 할만해서 또 도전할 예정
Code
import sys
from pprint import pprint
from collections import deque
input = sys.stdin.readline
field = []
for _ in range(12):
a = input().strip()
field.append([b for b in a])
def BFS(s, y, x):
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
visited = [[False for _ in range(6)] for _ in range(12)]
memory = [[y, x]]
visited[y][x] = True
q = deque()
q.append([y, x])
while q:
y, x = q.pop()
for dy, dx in d:
ny, nx = y + dy, x + dx
if (
0 <= ny < 12
and 0 <= nx < 6
and not visited[ny][nx]
and field[ny][nx] == s
):
visited[ny][nx] = True
q.append([ny, nx])
memory.append([ny, nx])
return memory
def rebase():
for i in range(11, -1, -1):
for j in range(6):
if field[i][j] == ".":
continue
move(i, j)
def move(y, x):
cur = y + 1
while True:
if cur >= 12 or field[cur][x] != ".":
break
cur += 1
if cur - 1 != y:
field[cur - 1][x] = field[y][x]
field[y][x] = "."
ans, flag = 0, True
while flag:
flag = False
for i in range(len(field)):
for j in range(len(field[0])):
if field[i][j] == ".":
continue
coordinates = BFS(field[i][j], i, j)
if len(coordinates) < 4:
continue
for y, x in coordinates:
field[y][x] = "."
flag = True
# pprint(field)
rebase()
# pprint(field)
if flag:
ans += 1
print(ans)