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

 문제에서 요구하는 것은 다음과 같다고 생각한다.

• 데이터를 입력받아 코어의 좌표를 받아올 수 있는가?
• 각 코어에 전선을 놓는 경우에 대해서, 백트래킹 기법을 이용해 전선이 놓이는 모든 경우를 구할 수 있는가?
• 전선을 놓는 모든 경우의 수 중, 가장 전선이 많이 놓이는 경우와 그 길이의 합이 최소일 때를 효과적으로 찾을 수 있는가?

 이 문제의 핵심이 되는 아이디어는 백트래킹으로의 접근이라고 본다. 하지만 그 결이 조금은 다른데, 전선을 놓는것을 기준으로 봤을 때 백트래킹을 설계한다면 전선을 놓을 수 없는 경우에 가지치기를 해야하나 이 문제에서는 해당 노드를 아예 건너뛰어 버리는 경우까지 고려한다. 결국 모든 노드에대해 전선을 놓을 네가지 방향을 전부 완전탐색을 해준다면 그 경우만 해도 벌써 16,000,000번이 넘으며, 전선을 놓는 연산까지 생각하면 분명 시간초과가 걸릴것이라고 생각했다. 따라서 이 부분을 해결하기 위해 전선을 놓아보기 전 탐색할 노드의 개수를 최대한 줄여봐야 하는데, 아예 전선을 놓을 수 없는 경우, 그리고 보드 둘레에 설치된 코어는 제외하도록 했다. 그 이후는 백트래킹을 이용해 노드들에 대해 전선을 놓아보고, 또 전선을 그려보는 함수를 구현하여 마무리한다. 맛보기 문제였으나, 난이도가 꽤 있는 문제라고 생각한다.

import heapq

t = int(input())

length_list = []
boards = []
# 주어진 입력 변수 저장
for i in range(t):
    n = int(input())
    length_list.append(n)
    result = []
    for j in range(n):
        result.append(list(map(int, input().split())))
    boards.append(result)
# 벽을 만나기 전, 혹은 다른 전선을 만나기 전까지 보드에 전선을 그려주는 메서드.
# 원상복구를 위해 백트래킹.
def draw_wire(_board,row,col,wire,distance):
    nRow, nCol = row + wire[0], col + wire[1]
    if _board[nRow][nCol] == 2:
        return (-1,_board)
    elif _board[nRow][nCol] == 3:
    	# new_board가 가리키게 되는것은 mutable하므로, 새로이 객체를 만들어 가리키게 할 수 밖에 없다.
        new_board = [[*elem] for elem in _board]
        return (distance+1,new_board)
    _board[nRow][nCol] = 2
    result = draw_wire(_board,nRow,nCol,wire,distance+1)
    _board[nRow][nCol] = 0
    return result if result[0] != -1 else (-1,_board)
# 와이어링을 하는경우와 하지 않는 경우 모두 고려해서 백트래킹을 해야한다.
def wiring(idx,nodes,wires,_board,length,cnt):
    if idx == len(nodes):
        heapq.heappush(li,(-cnt,length))
        return
    row,col = nodes[idx]
    for wire in wires[nodes[idx]]:
        temp = draw_wire(_board,row,col,wire,-1)
        if temp[0] != -1:
            cnt += 1
            length += temp[0]
            wiring(idx+1,nodes,wires,temp[1],length,cnt)
            cnt -= 1
            length -= temp[0]
    wiring(idx + 1, nodes, wires, _board, length, cnt)

for i, board in enumerate(boards):
    n = length_list[i]
    board = [[3] * (n + 2)] + [[3, *elem, 3] for elem in board] + [[3] * (n + 2)]
    wires = {}
    for row in range(2, n):
        for col in range(2, n):
            if board[row][col] == 1:
                wires[(row,col)] = []
                has_left = not any([board[row][j] for j in range(1,col)])
                if has_left: wires[(row,col)].append((0,-1))
                has_right = not any([board[row][j] for j in range(col+1,n+1)])
                if has_right: wires[(row,col)].append((0,1))
                has_upper = not any([board[i][col] for i in range(1,row)])
                if has_upper: wires[(row,col)].append((-1,0))
                has_lower = not any([board[i][col] for i in range(row+1,n+1)])
                if has_lower: wires[(row,col)].append((1,0))
                if not wires[(row,col)]:
                    del wires[(row,col)]

    nodes = list(wires.keys())
    li = []
    wiring(0,nodes,wires,board,0,0)
    print(f'#{i+1} {heapq.heappop(li)[1]}')