SWEA 1767 프로세서 연결하기

dfs와 백트래킹을 사용해 해결하는 문제이다.

연결이 불가능한 코어는 코어 리스트에서 아예 제외를 하고 연결이 가능한 코어중에서 하나씩 연결해보고 백트래킹 하면서 찾아가면 된다.

처음에 잘못 풀었던 부분은, 무작정 최소길이를 찾으려 해서 오답이 났다.
문제 조건에서 가능한 최대로 연결하고, 그 경우 중에서 최소길이를 찾아야 했다.

그래서 함수 실행중에 남은 코어갯수 + 연결한 코어갯수가 최대한 연결한 코어개수보다 작으면 함수를 종료해 가지치기를 하였다.

import math
import copy
t = int(input())
for _ in range(t):
    ans = math.inf
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    n = int(input())
    arr = []
    core = []
    maxcore = 0
    for i in range(n):
        arr.append(list(map(int,input().split())))
    for i in range(1,n-1):
        for j in range(1,n-1):
            if arr[i][j] == 1:
                core.append((i,j))

    def solve(cnt, psum, core, arr, connect):
        global ans
        global maxcore
        if len(core) - cnt + connect < maxcore:
            return
        if cnt == len(core):
            if connect == maxcore:
                ans = min(ans,psum)
            elif connect > maxcore:
                maxcore = connect
                ans = psum
            return
        x, y = core[cnt]
        for i in range(4):
            darr = copy.deepcopy(arr)
            nx = x + dx[i]
            ny = y + dy[i]
            move = 0
            while 0 <= nx < n and 0 <= ny < n:
                if darr[nx][ny] == 1:
                    move = 0
                    break
                else:
                    move += 1
                    darr[nx][ny] = 1
                    nx = nx + dx[i]
                    ny = ny + dy[i]
            if move == 0:
                continue
            else:
                solve(cnt + 1, psum + move,core, darr,connect + 1)
        ## 연결 안한 경우
        solve(cnt + 1,psum,core,arr, connect)

    solve(0, 0, core,arr, 0)
    del core[:]
    print(f"#{_+1} {ans}")