[SWEA] 1767. 프로세서 연결하기 - Python

문제 정보

• 문제 이름: 1767. [SW 역량테스트] 프로세서 연결하기
• 문제 링크: SW Expert Academy 1767번
• 알고리즘 분류: 시뮬레이션, 완전 탐색 (DFS), 백트래킹 (Backtracking)

---

풀이 과정

1. 문제 분석 및 제약 조건 확인

• 가장자리 코어의 특징: 격자의 가장자리(경계선)에 붙어 있는 코어는 이미 전선이 연결된 상태로 간주한다. 따라서 직접 전선을 연결해 줄 필요가 없으므로 탐색 대상에서 제외해야 한다.
• 코어 연결 조건:
  • 하나의 코어는 상, 하, 좌, 우 4방향 중 한 방향으로만 전선을 뻗을 수 있다.
  • 전선은 일직선으로만 뻗어나가며, 가는 길에 다른 코어나 이미 설치된 전선이 있으면 안 된다.
• 최적화 목표:
  1. 최대한 많은 코어를 연결하는 것이 1순위 목표다.
  2. 연결한 코어 수가 같다면, 전선 길이의 합이 최소가 되는 경로를 찾아야 한다.
• 제약 조건: 코어의 개수는 최대 12개다. 각 코어마다 5가지 선택지(상, 하, 좌, 우, 연결 안 함)가 있으므로 이론상 최대 $5^{12}$ (약 2억 4천만)의 경우의 수가 생긴다. 이를 제한 시간 내에 해결하려면 효율적인 가지치기(Pruning)가 필수적이다.

2. 알고리즘 및 자료구조 선택

• DFS (깊이 우선 탐색): 코어를 하나씩 차례대로 확인하며 가질 수 있는 모든 방향의 선택지를 깊이 탐색하기에 가장 적합하다.
• 백트래킹 (Backtracking):
  • "코어 1을 위로 연결해 본 다음, 탐색이 끝나면 다시 전선을 지우고 아래로 연결해 보기" 처럼, 이전 상태로 맵을 원상복구(grid[r][c] = 0)하는 백트래킹 기술이 핵심이다.
• 가지치기 (Pruning):
  • 현재까지 연결한 코어 수 + 앞으로 남은 코어의 수 < 여태까지 구한 최대 연결 코어 수
  • 위 조건에 해당한다면, 남은 코어를 전부 연결하더라도 기존 기록을 경신할 수 없다. 따라서 즉시 탐색을 종료(return)하여 낭비되는 연산을 획기적으로 줄인다.

3. 절차적 구현 흐름

1. 내부 코어 수집: 이중 포문을 돌되, 인덱스 범위를 1부터 N-2로 설정하여 가장자리를 제외한 내부 코어의 좌표만 cores 리스트에 담는다.
2. 사방 탐색 및 전선 설치 함수 구현:
   • can_place(y, x, dir): 특정 방향으로 끝까지 갈 수 있는지 검사한다. 가는 길에 1(코어)이나 2(전선)를 만나면 False를 반환한다.
   • set_wire(y, x, dir, val): 갈 수 있다면 맵에 전선 표시(val=2)를 하며 전선의 길이를 누적해 반환한다. 이 함수는 백트래킹 시 전선을 지우는 용도로도 재활용한다.
3. DFS 탐색 실행:
   • [가지치기] 남은 코어를 다 더해도 가망이 없다면 즉시 탐색을 종료한다.
   • [기저 조건] 모든 코어를 다 확인했을 때 (index == total_cores):
     • 새로 찾은 연결 수가 기존 최대 수보다 많다면, 기존 기록은 쓸모없어지므로 max_cores와 min_length를 새 값으로 완전히 덮어씌운다.
     • 연결 수가 기존 최대 수와 같다면, 전선 길이(wire_length)의 최솟값을 비교해 갱신한다.
   • [사방 탐색] 현재 코어에서 4방향을 검사하여 놓을 수 있는 방향이 있다면 선을 깔고(set_wire(..., 2)) 다음 재귀로 넘어간 뒤, 돌아왔을 때 다시 선을 지운다(set_wire(..., 0)).
   • [건너뛰기] 사방 탐색이 끝나면, "이 코어는 연결을 포기하고 다음 코어로 넘어가기"(dfs(index + 1, connected, wire_length))를 호출하여 유연하게 최선의 조합을 찾는다.

4. 시간 복잡도

• 모든 코어가 가질 수 있는 선택지는 최대 5가지이므로 기본 시간 복잡도는 $O(5^M)$ ($M$은 내부 코어의 개수, $M \le 12$) 이다.
• 매 탐색 단계에서 방향성을 검사하고 전선을 까는 데 격자 크기 $N$ 만큼의 연산이 추가되어 $O(N \cdot 5^M)$ 이 된다.
• 하지만 실제로는 이미 놓인 전선들에 가로막혀 더 이상 깊이 들어가지 못하는 경우가 매우 많고, 무엇보다 강력한 가지치기 조건이 적용되어 있어 실질적인 시간 복잡도는 탐색 트리 크기의 극히 일부분만 수행하게 된다. 덕분에 제한 시간 2초 이내에 매우 여유롭게 통과할 수 있다.