Info

• 문제 링크: https://www.acmicpc.net/problem/16768
• solved 티어: gold 4
• 맞은 비율: 52.4%
• 결과: 성공

내 풀이

import sys
sys.setrecursionlimit(1000000)

def read():
    return sys.stdin.readline().strip()

class Mooyo:
    def __init__(self):
        self.vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        self.n, self.k = map(int, read().split())
        self.board = [list(map(int, list('0' + read() + '0'))) for _ in range(self.n)]
        self.board = [[0 for _ in range(12)]] + self.board + [[0 for _ in range(12)]]
        self.check = [[0 for _ in range(12)] for _ in range(self.n + 2)]
        self.dfs_stack = []

    def main(self):
        while True:
            changed = self.check_stage()
            if changed:
                self.pull_down()
            else:
                break
        self.print_board()

    def check_stage(self):
        changed = False
        self.check = [[0 for _ in range(12)] for _ in range(self.n + 2)]
        for i in range(1, self.n + 1):
            for j in range(1, 10 + 1):
                c = self.board[i][j]
                if c and not self.check[i][j]:
                    self.dfs_stack = []
                    adjacent = self.search_dfs(i, j)
                    if adjacent >= self.k:
                        changed = True
                        self.kill_adj()
                    self.dfs_stack = []
        return changed

    def search_dfs(self, y, x):
        self.check[y][x] = 1
        self.dfs_stack.append((y, x))
        adj = 1
        for i in range(4):
            yy, xx = y + self.vec[i][0], x + self.vec[i][1]
            if self.board[yy][xx] == self.board[y][x] and not self.check[yy][xx]:
                adj += self.search_dfs(yy, xx)
        return adj

    def kill_adj(self):
        for y, x in self.dfs_stack:
            self.board[y][x] = 0

    def pull_down(self):
        for j in range(1, 10 + 1):
            nonzeros = [self.board[i][j] for i in range(self.n, 0, -1) if self.board[i][j]]
            fill = nonzeros + [0 for _ in range(0, self.n - len(nonzeros))]
            for i, f in zip(range(self.n, 0, -1), fill):
                self.board[i][j] = f

    def print_board(self):
        for i in range(1, self.n+1):
            print(''.join(map(str, self.board[i][1:-1])))


mooyo = Mooyo()
mooyo.main()