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

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

---

 

25/07/29

 

 

구현에서 실수가 날 수도 있는 약간 까다로운 백트래킹 문제이다.

---

 

문제 접근 방식:

 

 

문제에서 요구하는 상황은 다음과 같다.

 

현재 코어가 놓여있고, MAP의 가장자리에는 전기가 흐른다. 가장자리에 놓여있는 코어는 전기가 이미 흐른다고 간주한다.

 

우리가 구하고자 하는 것은, 코어에 전선을 연결하여 최대한 많은 코어에 전기를 흘리고자 할 때 그때 전선 길이의 합의 최솟값을 구하는 것이다.

 

이때 코어에서 가장자리로 연결하는 전선은 서로 교차할 수 없고, 일직선의 형태이다.

 

 

일단 문제를 보면, 맵의 크기가 상당히 작고, $7 \leq N \leq 12$라고 주어져있기 때문에, 완전 탐색을 해도 충분할 것이라는 믿음이 존재한다.

 

기본적인 방법은 코어를 하나 선택하고, 해당 코어에서 위, 아래, 왼쪽, 오른쪽 중 하나의 방향으로 뻗어나가는 전선을 하나 놓고, 다음 코어를 보는 것이다. 이후 다른 방향으로 뻗어나가는 전선을 놓기 위해 놓인 전선을 회수해야 한다.

 

최종적으로 모든 코어를 다 볼 시점에 전선 길이의 합을 구해준 다음, 전선 길이의 합의 최솟값을 갱신해준다.

 

저렇게 구현하고 예제를 돌렸는데, 예제에서 잘못된 답을 내뱉었다.

 

 

첫번째로 했던 실수는, 전선을 놓고 회수하는 로직을 잘못 짠 것이다.

 

빈 칸에 놓고, 아니면 못놓는다고 한 후에 회수할 때 전선만 회수해야 하는데 코어와 같이 회수한 것이다.

 

해당 문제를 해결한 후에, 예제를 돌렸는데 잘못된 답이 나왔다.

 

 

두번째로 했던 실수는, 전선 길이의 합의 최솟값을 갱신할 때 코어의 개수를 고려하지 않았다는 점이다.

 

연결되는 코어의 개수가 최대가 되면서, 동시에 전선 길이의 합의 최솟값을 구해야하기 때문에 DFS를 돌리면서 인자로 지금까지 연결되었던 코어의 개수를 인자로 넘기는 방향으로 코드를 고쳤다.

 

이후 예제가 잘 나와서 제출을 했는데, 60개의 테스트 케이스 중 55개만 맞았다.

 

 

세번째로 했던 실수는, Impossible_flag를 세워두고, 어떤 방향에서도 코어에 전선을 놓을 수 없을 경우에만 해당 코어에 전선을 연결하지 않고 다음 코어를 탐색하도록 구현한 것이다.

 

실제로는 현재 내가 보고있는 코어에 전선을 이어버리지 않고 다음 코어에 전선을 연결함으로써 더 많은 코어에 전선을 연결할 수도 있다.(혹은 같은 개수의 코어에 더 적은 전선을 사용할 수도 있다.)

 

이를 고려하여, Impossible_flag를 세워두지 않고 그냥 $4$방향 탐색 이후에 코어에 전선을 놓지 않는 경우까지 그냥 탐색하도록 코드를 수정함으로써 AC를 받을 수 있었다.  

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

ans = 10000000
max_matched = 0

def dfs(POS, MAP, idx, matched):
    global ans, max_matched
    if idx == len(POS): # 현재 보고있는 코어가 더 이상 존재하지 않는다면
        N = len(MAP)
        line = 0
        # 그려진 라인의 수를 센다.
        for i in range(N):
            for j in range(N):
                if MAP[i][j] == 2:
                    line += 1
        # 이때 지금까지 매칭되었던 코어의 개수가 더 같을 때, ans를 라인과 ans의 최솟값으로 갱신한다.
        if matched == max_matched and line < ans:
            ans = line
        # 만약 지금까지 매칭되었던 코어의 개수가 더 많다면, ans를 line으로 갱신한다.
        elif matched > max_matched:
            max_matched = matched
            ans = line
        return
    # 현재 MAP의 크기 선언
    N = len(MAP)
    # 지금 전원을 연결할 코어의 위치를 보자.
    core_r, core_c = POS[idx]
    # 만약 이 코어가 가장 자리에 있다면
    if core_r == 0 or core_r == N-1 or core_c == 0 or core_c == N-1:
        dfs(POS, MAP, idx+1, matched+1) # 이미 연결되어 있다.
        return
    # 코어가 가장자리에 있지 않다면 연결해줘야한다.
    # 연결이 가능한지의 여부를 따지는 impossible_flag를 세운다.
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
    for i in range(4): # 방향을 하나 정해서 쭉 가자
        flag = True # 해당 방향으로 전선을 놓을 수 있는지의 여부를 알려주는 flag를 세운다.
        k = 1
        while True:
            nr, nc = core_r+k*dr[i], core_c+k*dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if MAP[nr][nc] == 0: # 빈 칸일때만 전선을 놓는다.
                    MAP[nr][nc] = 2
                    k += 1 # 앞으로 전진
                else: # 코어거나, 이미 전선이 놓여있는 경우 해당 방향으로 전선을 놓지 못한다.
                    k -= 1 # 뒤로 후퇴
                    flag = False
                    break
            else:
                k -= 1
                break
        if flag: # 해당 방향으로 전선을 놓을 수 있는 경우
            dfs(POS, MAP, idx+1, matched+1)
        # 전선을 놓다가 끊기거나, 전선을 못놓았거나, 전선을 성공적으로 해당 방향으로 놓았다면
        # 이제 회수할 차례이다.
        while True:
            nr, nc = core_r+k*dr[i], core_c+k*dc[i]
            if nr < 0 or nr >= N or nc < 0 or nc >= N:
                k -= 1
            elif k > 0 and MAP[nr][nc] == 2: # 전선이 놓아져있다면 빈칸으로 다시 복구
                MAP[nr][nc] = 0
                k -= 1
            else:
                break
    dfs(POS, MAP, idx+1, matched)
    return

def solve(test_case_num):
    global ans, max_matched
    ans, max_matched = 10000000, 0
    N = int(input())
    MAP = [list(map(int, input().split())) for _ in range(N)]
    POS = []
    for i in range(N):
        for j in range(N):
            if MAP[i][j]:
                POS.append((i, j))
    dfs(POS, MAP, 0, 0)
    print(f'#{test_case_num} {ans}')
    return

def main():
    T = int(input())
    for i in range(1, T + 1):
        solve(i)

main()