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

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf 

SW Expert Academy

어렵게 생각해서 백트레킹을 통한 완탐을 하면 안된다고 생각해서 못 푼 문제다.

시간을 보면 python의 경우 8초고 N의 크기가 7~12까지라서 빅 O(N^4)을 해도 8초가 넘지 않는다.

 

크게 생각나는 방법이 두가지가 있다.

하나는 가장자리에 있지 않은 1의 좌표를 찾아내고 백트래킹을 통해

1. 연결 x

2. dy -1로 연결

3. dy +1로 연결

4. dx -1로 연결

5. dx +1로 연결

총 5가지 경우의 수로 백트래킹을 돌리는 것

 

두번째로는 combination을 통해 조합을 미리 구하는 것이다.

 

첫번째 방법은 함수의 argument로 리스트를 넘겨야하고, 리스트를 복사해야하는 시간적, 메모리적 부담감이 있지만

구현은 그만큼 쉽다.

 

두번째 방법은 조합을 통해서 미리 골라두고 돌리는 것

 

나는 첫번째 방법을 하기로 했다.

 

첫번째로는 backtracking 함수를 구현하고

두번째로는 check 함수를 통해서 유효한 좌표인지 확인한다

 

생각해야할 것은 backtracking의 종료 조건

코어를 끝까지 탐색했을 경우이다.

 

근데 여기서 또 나뉨

코어를 다 연결했는가 vs 일부분만 연결했는가

 

그 다음에 또 최적화할 부분

이미 모든 코어에 전원이 들어오면 굳이 아무것도 연결하지 않는 것을 연결해줄 필요는 없음

 

d = [(-1,0),(1,0),(0,-1),(0,1)]

def check(y,x):
    return 0 <= y < N and 0 <= x < N

def backtracking(n,cnt,core,lst):
    global answer, core_if, core_answer
    now_lst = list(lst[i][:] for i in range(N))
    if n == len(one):
        if core == len(one):
            answer = min(answer, cnt)
            core_if = len(one)
        elif core_if < core:
            core_if = core
            core_answer = cnt
        elif core_if == core:
            core_answer = min(core_answer, cnt)
        return
    y, x = one[n]
    if not core_if == len(one):
        backtracking(n + 1, cnt, core, now_lst)
    for i in range(4):
        visited = []
        dy,dx = d[i]
        ny = y + dy
        nx = x + dx
        while check(ny,nx) and now_lst[ny][nx] == 0:
            now_lst[ny][nx] = 1
            visited.append((ny,nx))
            ny += dy
            nx += dx
        if check(ny,nx) and now_lst[ny][nx] == 1:
            for vy,vx in visited:
                now_lst[vy][vx] = 0
            continue
        backtracking(n+1,cnt+len(visited),core+1,now_lst)
        for vy, vx in visited:
            now_lst[vy][vx] = 0

T = int(input())

for t in range(1,T+1):
    N = int(input())
    lst = []
    one = []
    for y in range(N):
        tmp = list(map(int,input().split()))
        for x in range(1,N-1):
            if tmp[x] == 1 and y not in [0,N-1]:
                one.append((y,x))
        lst.append(tmp)
    answer = N**2
    core_answer = N**2
    core_if = 0
    backtracking(0,0,0,lst)
    if core_if != len(one):
        answer = core_answer
    print(f'#{t} {answer}')