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

1. 코드(BFS)

from collections import deque


def check(char, i, j):
    width = 1
    temp = [(i, j)]
    q = deque()
    q.append((i, j))
    visited[i][j] = True
    while q:
        x, y = q.popleft()
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = x+dx, y+dy
            if 0<=nx<12 and 0<=ny<6:
                if graph[nx][ny] == char and not visited[nx][ny]:
                    width += 1
                    temp.append((nx, ny))
                    visited[nx][ny] = True
                    q.append((nx, ny))
    if width >= 4:
        for x, y in temp:
            graph[x][y] = '.'
        return True



ans = 0
graph = [list(map(str, input())) for _ in range(12)]
while True:
    flag = False
    remove = []
    visited = [[False] * 6 for _ in range(12)]

    # 알파벳 제거
    for i in range(12):
        for j in range(6):
            if graph[i][j] != '.' and not visited[i][j]:
                if check(graph[i][j], i, j):
                    flag = True

    # 알파벳 하강
    for _ in range(12):
        for i in range(11):
            for j in range(6):
                if graph[i + 1][j] == '.':
                    graph[i + 1][j], graph[i][j] = graph[i][j], '.'

    if not flag:
        break
    else:
        ans += 1
print(ans)

2. 코드(DFS)

def check(char, i, j):
    def dfs(x, y):
        if not (0 <= x < 12 and 0 <= y < 6):
            return
        if not visited[x][y] and graph[x][y] == char:
            visited[x][y] = True
            temp.append((x, y))
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)

    temp = []
    dfs(i, j)
    if len(temp) >= 4:
        for x, y in temp:
            graph[x][y] = '.'
        return True



ans = 0
graph = [list(map(str, input())) for _ in range(12)]
while True:
    flag = False
    remove = []
    visited = [[False] * 6 for _ in range(12)]

    # 알파벳 제거
    for i in range(12):
        for j in range(6):
            if graph[i][j] != '.' and not visited[i][j]:
                if check(graph[i][j], i, j):
                    flag = True

    # 알파벳 하강
    for _ in range(12):
        for i in range(11):
            for j in range(6):
                if graph[i + 1][j] == '.':
                    graph[i + 1][j], graph[i][j] = graph[i][j], '.'

    if not flag:
        break
    else:
        ans += 1
print(ans)