[SWEA] 프로세서 연결하기

[SW Test 샘플문제] 프로세서 연결하기

import sys

input = sys.stdin.readline

N, board, answer, max_core_cnt, core, bfs = [None] * 6
dxdy = [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0)]


def init():
    global N, board, answer, max_core_cnt, core, bfs
    N = int(input())
    board = []
    answer = N ** 2
    max_core_cnt = 0
    core = []
    bfs = None

    for n in range(N):
        board.append(list(map(int, input().split(' '))))

    for i, row in enumerate(board):
        for j, col in enumerate(row):
            if (0 < i < N - 1) and (0 < j < N - 1) and col == 1:
                core.append((i, j))


def list_to_str(list_):
    str_ = ''
    for r in list_:
        str_ += ''.join(map(str, r))
    return str_


def str_to_list(s):
    result_l = []
    temp_l = list(map(int, list(s)))
    for index in range(N):
        result_l.append(temp_l[index * N:(index + 1) * N])
    return result_l


def connect_core(temp_core, direct, temp_board):
    temp_board = str_to_list(temp_board)
    dist_cnt = 0
    x, y = temp_core
    dx, dy = dxdy[direct]
    while 0 <= x + dx < N and 0 <= y + dy < N:
        if temp_board[x + dx][y + dy] != 0:
            return False

        temp_board[x + dx][y + dy] = 2
        dist_cnt += 1
        x += dx
        y += dy
    return dist_cnt, list_to_str(temp_board)


def solve():
    global N, board, answer, max_core_cnt, core, bfs, dxdy
    bfs = [(0, 0, 0, list_to_str(board))]

    while bfs:
        core_cnt, core_idx, dist, board_s = bfs.pop()

        if len(core) - core_idx + core_cnt < max_core_cnt:
            continue

        if core_idx == len(core):
            if max_core_cnt < core_cnt:
                answer = dist
                max_core_cnt = core_cnt
            elif max_core_cnt == core_cnt:
                answer = min(answer, dist)

            continue

        cur_core = core[core_idx]
        for dir_ in range(5):
            if dir_ == 0:
                bfs.append((core_cnt, core_idx + 1, dist, board_s))
            else:
                result = connect_core(cur_core, dir_, board_s)
                if not result:
                    continue
                next_dist, next_board = result
                bfs.append((core_cnt + 1, core_idx + 1, dist + next_dist, next_board))


def main():
    T = int(input())
    for test_case in range(1, T + 1):
        init()
        solve()
        print(f"#{test_case} {answer}")


main()