[SWEA] 1767_프로세서 연결하기

📕 문제

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

SW Expert Academy

 

💡 풀이법

1. 전선의 길이를 구해주는 length_wire 라는 함수를 만들어준다.

2. 코어들의 좌표와 전선이 방향이 담길 cores라는 리스틀 만든다.

3. 그래프를 돌면서 코어가 있는데 벽에 붙어있는 코어라면 좌표와 5가 담긴 리스트를 cores에 넣는다.

벽에 붙어있는 코어가 아니라면 좌표와 -1이 담긴 리스트를 cores에 넣는다.

4. dfs의 첫번째 인자는 현재 보고 있는 코어이고, cnt는 지금까지 전원이 연결된 코어의 개수이다.

5. 만약 지금까지의 cnt에 남은 코어의 개수를 다 더해도 ans보다 작다면 재귀 멈춤. (가지치기)

6. n이 core의 개수보다 크거나 같으면 모든 코어를 확인했기 때문에 return을 할거임. (베이스 라인)

cnt가 ans보다 크다면 ans를 cnt로 바꾸고, 전선의 길이를 구해주는 함수를 실행하고 반환값을 ans_total에 넣는다

만약, cnt가 ans랑 같다면 전선의 길이를 비교해주고 현재 전선의 길이가 더 작다면 ans_total을 현재 전선의 길이로 바꾼다.

 

7. 현재 코어의 방향이 5라는 뜻은 벽면에 붙어있단 뜻이기 때문에 cnt를 +1해주고 다음 코어로 dfs를 돌린다.

8. 그렇지 않다면 현재 코어를 전원과 연결하는 경우랑 연결하지 않을 경우가 나뉠수 있기 때문에 먼저 연결하지 않고 다음 코어로 넘어가는 dfs를 실행시킨다. (이때, cnt는 증가시켜주지 않는다)

현재 코어를 전원과 연결하는 경우는 다른 코어들로 인해 방향이 막혀있지 않는지, 다른 코어를 연결한 전선으로 인해 막혀있는지 않는지를 확인해주어야 한다.

(이때, 다른 코어의 전선으로 인해 경로가 막혀있는지 아닌지를 봐주는 것은 현재 코어 전의 코어들에서만 봐주면 된다. 현재 코어 이후의 코어는 아직 전선이 정해져있지 않기 때문)

 

9. 다 확인해주고 가능한 방향마다 각각 dfs를 돌려준다. 이때, 현재 코어의 전선의 방향을 가능한 방향으로 바꿔주고 dfs를 실행이후에는 다시 -1로 바꿔주어야한다.

 

 

def length_wire(cores):
    total = 0
    for core in cores:  # left, up, right, down
        if core[2] == 0:
            total += core[1]
        elif core[2] == 1:
            total += core[0]
        elif core[2] == 2:
            total += N-core[1]-1
        elif core[2] == 3:
            total += N-core[0]-1
    return total

def dfs(n, cnt):
    global ans, ans_total
    if cnt + cores_cnt-n < ans:  # 가지치기
        return
    if n >= cores_cnt:  # 베이스 라인
        if cnt > ans:
            ans = cnt
            ans_total = length_wire(cores)
        elif cnt == ans:
            total = length_wire(cores)
            if total < ans_total:
                ans_total = total
        return

    x, y, z = cores[n]
    if cores[n][2] == 5:
        dfs(n+1, cnt+1)
    else:
        dfs(n+1, cnt)
        d = [1]*4  # left, up, right, down
        for m in range(0, n):    
            if x == cores[m][0]:
                d[0] = 0
            elif y == cores[m][1]:
                d[1] = 0
            elif x > cores[m][0] and y > cores[m][1]:
                if cores[m][2] == 2:
                    d[1] = 0
                elif cores[m][2] == 3:
                    d[0] = 0
            elif x > cores[m][0] and y < cores[m][1]:
                if cores[m][2] == 0:
                    d[1] = 0
                elif cores[m][2] == 3:
                    d[2] = 0
                
        for m in range(n+1, cores_cnt):
            if x == cores[m][0]:
                d[2] = 0
            elif y == cores[m][1]:
                d[3] = 0
        
        for i in range(4):
            if d[i] == 1:
                cores[n][2] = i
                dfs(n+1, cnt+1)
                cores[n][2] = -1


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    cores = []
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 1:
                if i == 0 or i == N-1 or j == 0 or j == N-1:
                    cores.append([i,j,5])
                else:
                    cores.append([i,j,-1])
        
    cores_cnt = len(cores)
    ans = ans_total = 0
    dfs(0, 0)
    print('#{} {}'.format(tc, ans_total))