프로그래머스 | Python | 완전탐색 | 전력망을 둘로 나누기 (Lv.2)

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

 

문제 해결: 트리 분할 후 완전 탐색

---

정답 코드(BFS)

from collections import deque

def bfs(node, graph, visited):
    count = 0
    queue = deque([node])
    visited[node] = True

    while queue:
        current = queue.popleft()
        count += 1
        for neighbor in graph[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

    return count

def solution(n, wires):
    # 결과 값을 매우 큰 값으로 초기화
    min_difference = float('inf')

    # 모든 전선을 순회하며 하나씩 끊어보기
    for i in range(len(wires)):
        # 그래프 생성
        graph = {i: [] for i in range(1, n + 1)}
        visited = [False] * (n + 1)  # 그래프 정의 후 방문 리스트 초기화
        for j, (v1, v2) in enumerate(wires):
            if i == j:  # i번째 전선을 끊는다.
                continue
            graph[v1].append(v2)
            graph[v2].append(v1)

        # BFS로 두 전력망의 크기를 구한다.
        # 첫 번째 전력망 크기
        size_one = bfs(1, graph, visited)
        # 두 번째 전력망 크기
        size_two = n - size_one

        # 두 전력망 크기의 차이를 계산
        min_difference = min(min_difference, abs(size_one - size_two))

    return min_difference

---

코드 설계 및 해설

1. 문제 분석

• 문제는 트리 형태의 그래프에서 하나의 간선을 제거하여 두 개의 서브트리로 나눌 때, 두 트리의 크기 차이를 최소화하는 것입니다.
• 트리 특징:
  •   노드 수: n.
  •   간선 수: n−1.
  •   하나의 간선을 제거하면 항상 두 개의 연결 컴포넌트로 나뉩니다.

---

2. 설계 방식

1) 간선 하나씩 끊어보기 (완전 탐색)

•   n−1개의 간선 중 하나를 제거합니다.
•   각 제거된 간선에 대해 나머지 그래프에서 두 연결 컴포넌트의 크기를 계산.

2) 그래프 표현

•   그래프는 인접 리스트를 사용해 표현:
•   graph = {1: [2, 3], 2: [1], 3: [1]}
•   이는 간선을 추가/제거하거나 탐색할 때 효율적입니다.

3) BFS를 통한 연결 컴포넌트 크기 계산

•   BFS를 사용하여 한 연결 컴포넌트의 크기를 계산합니다.
•   나머지 노드 수는 전체 노드 수 n에서 해당 크기를 빼서 구합니다.

4) 크기 차이 최소화

•   모든 간선을 끊어보면서 각 경우에 대해 두 서브트리 크기의 절대 차이를 계산.
•   최소 차이를 갱신.

---

3. 핵심 문법

1. deque를 활용한 BFS:
   •   BFS는 큐를 활용해 그래프를 레벨별로 탐색합니다.
   •   collections.deque를 사용해 큐를 효율적으로 구현.
2. graph 딕셔너리:
   •   그래프의 간선을 인접 리스트 형태로 표현.
3. visited 리스트:
   •   각 노드가 방문되었는지 확인하기 위한 리스트.
4. 완전 탐색:
   •   간선을 하나씩 제거하며 모든 경우를 확인.

---

count의 역할

•   탐색된 노드(송전탑)의 개수를 세는 변수입니다.
•   문제에서는 한 전력망에 속한 송전탑의 총 개수를 반환합니다.
•   두 전력망 크기의 차이를 계산하기 위해 사용됩니다.

---

count += 1의 위치와 역할

count += 1은 BFS 탐색 과정에서 현재 노드가 탐색되었음을 기록하는 역할을 합니다. 현재 위치에서 count += 1이 실행되는 이유는 큐에서 노드를 꺼낸 시점이 바로 해당 노드를 탐색 완료한 시점이기 때문입니다.

 

• count += 1은 현재 노드를 방문할 때마다 실행됨.
• 즉, 각 노드를 방문할 때마다 count가 증가.
• bfs()가 종료되면 count는 현재 연결된 그래프(전력망)의 크기를 나타냄.

 

---

visited 리스트의 크기가 n+1인 이유

노드 번호가 1부터 시작하기 때문입니다. Python에서 리스트의 인덱스는 0부터 시작하지만, 이 문제에서는 송전탑(노드)의 번호가 1부터 n까지 주어지므로, 이를 맞추기 위해 visited 리스트의 크기를 n+1로 설정합니다.

---

BFS 탐색의 기본 구조

1. 큐에 노드를 추가:
   •   다음에 탐색할 노드를 큐에 넣습니다.
   •   아직 탐색되지 않은 노드입니다.
2. 큐에서 노드를 꺼냄 (queue.popleft()):
   •   이제 탐색할 차례가 된 노드를 큐에서 꺼냅니다.
   •   이 시점이 "탐색 완료"로 간주됩니다.
3. 탐색된 노드 개수 증가 (count += 1):
   •   탐색이 완료된 노드의 개수를 기록합니다.
4. 현재 노드의 이웃 노드 탐색:
   •   아직 방문하지 않은 이웃 노드를 찾아 큐에 추가합니다.

---

코드 동작 흐름

예제 그래프:

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2]
}

BFS 실행:

visited = [False] * 5  # 총 4개의 노드 (1~4 사용)
count = bfs(1, graph, visited)

1. 초기 상태:
   • queue = [1] (탐색 시작 노드: 1).
   • visited = [False, True, False, False, False].
   • count = 0.
2. 첫 번째 반복:
   • current = queue.popleft() → current = 1.
   • count += 1 → count = 1 (1번 노드 탐색 완료).
   • 이웃 노드 2, 3 추가:
     • queue = [2, 3].
     • visited = [False, True, True, True, False].
3. 두 번째 반복:
   • current = queue.popleft() → current = 2.
   • count += 1 → count = 2 (2번 노드 탐색 완료).
   • 이웃 노드 4 추가:
     • queue = [3, 4].
     • visited = [False, True, True, True, True].
4. 세 번째 반복:
   • current = queue.popleft() → current = 3.
   • count += 1 → count = 3 (3번 노드 탐색 완료).
   • 이웃 노드 모두 방문됨 → 큐 변경 없음.
5. 네 번째 반복:
   • current = queue.popleft() → current = 4.
   • count += 1 → count = 4 (4번 노드 탐색 완료).
   • 이웃 노드 모두 방문됨 → 큐 변경 없음.
6. 종료:
   • queue가 비었으므로 반복 종료.
   • 반환값: count = 4.

---

❕for j, (v1, v2) in enumerate(wires):

1. wires의 구조

wires는 리스트이지만, 그 안에 각 원소가 리스트 또는 튜플 형태로 저장되어 있습니다.

예제:

wires = [[1, 3], [2, 3], [3, 4]]

•   wires는 리스트이고,
•   wires[0] = [1, 3] → 이 안에는 두 개의 숫자가 들어 있는 또 다른 리스트입니다.

 

2. for j, (v1, v2) in enumerate(wires)의 동작

 

1) enumerate(wires) 동작

enumerate(wires)는 반복 가능한 객체(wires)를 인덱스와 값으로 나눠서 반환합니다.

 

예를 들어:

for j, wire in enumerate(wires):
    print(j, wire)

 

출력:

0 [1, 3]
1 [2, 3]
2 [3, 4]

• j: 현재 인덱스 (0, 1, 2...).
• wire: 현재 원소 ([1, 3], [2, 3], [3, 4]).

2) (v1, v2) 언패킹

wire가 [1, 3]처럼 두 개의 값을 가진 리스트나 튜플이라면, 이를 v1, v2로 바로 분리할 수 있습니다.

for j, (v1, v2) in enumerate(wires):
    print(j, v1, v2)

 

출력:

0 1 3
1 2 3
2 3 4

• (v1, v2)는 wire의 첫 번째 값과 두 번째 값을 각각 v1과 v2로 나눕니다.
• 이 과정은 언패킹(unpacking)으로 불립니다.

 

3. 왜 (v1, v2)가 가능한가?

Python에서 리스트나 튜플을 반복문에서 바로 변수로 언패킹할 수 있는 기능 때문입니다.

 

예:

pairs = [[1, 2], [3, 4], [5, 6]]

for a, b in pairs:
    print(a, b)

 

출력:

1 2
3 4
5 6

---

❕continue가 전선을 끊는 역할을 하는 이유

코드의 핵심

for i in range(len(wires)):  # 모든 전선에 대해 반복
    graph = {i: [] for i in range(1, n + 1)}  # 그래프 초기화
    for j, (v1, v2) in enumerate(wires):  # wires의 모든 전선을 순회
        if i == j:  # i번째 전선(wires[i])를 제외
            continue  # 이 전선을 건너뛰고 다음 전선으로 진행
        graph[v1].append(v2)  # 나머지 전선을 그래프에 추가
        graph[v2].append(v1)

 

 

continue가 하는 일

continue 동작:

•   현재 반복을 종료하고, 다음 반복으로 넘어갑니다.
•   즉, if i == j 조건이 참일 때, 현재 j번째 전선을 무시하고 나머지 전선을 처리하게 됩니다.

구체적인 동작:

1. for j, (v1, v2) in enumerate(wires)는 모든 전선의 (v1, v2)를 하나씩 순회.
2. if i == j: 조건이 참이면:
   •   현재 j번째 전선 (v1, v2)는 그래프에 추가하지 않고 건너뜀.
3. 나머지 전선만 그래프에 추가.

---

왜 continue가 전선을 끊는 역할을 하는가?

1. 특정 전선을 제외하려면

•   전선을 "끊는다"는 것은 해당 전선을 그래프에서 제외하는 것을 의미합니다.
•   continue를 통해 특정 전선 (v1, v2)만 그래프에 포함되지 않도록 처리.

2. 끊은 전선을 제외한 그래프를 생성

•   if i == j: continue는 i번째 전선을 무시하고 넘어가도록 설정.
•   결과적으로, 해당 전선을 포함하지 않는 새로운 그래프가 만들어짐.

---

예시 입력

n = 9
wires = [[1, 3], [2, 3], [3, 4], [4, 5], [4, 6], [4, 7], [7, 8], [7, 9]]
print(solution(n, wires))

코드의 흐름

1. 초기 상태

•   n = 9: 송전탑의 개수.
•   wires: 전선의 연결 관계.

 

2. 전선 하나씩 끊기 (for i in range(len(wires)))

•   전선 하나씩 제거하면서 나머지로 그래프를 구성.

 

첫 번째 반복 (i = 0)

•   끊는 전선: [1, 3].
•   그래프 구성:
•   graph = { 1: [], 2: [3], 3: [2, 4], 4: [3, 5, 6, 7], 5: [4], 6: [4], 7: [4, 8, 9], 8: [7], 9: [7] }

 

BFS 탐색

첫 번째 전력망 크기 (size_one):

1. BFS 시작: node = 1.
2. 큐 초기 상태: queue = deque([1]).
3. graph[1] = [] (이웃이 없음) → 탐색 종료.
4. size_one = 1 (노드 1만 포함).

두 번째 전력망 크기 (size_two):

•   size_two = n - size_one= 9 - 1 = 8.

크기 차이 계산:

•   ∣1−8∣=7
•   현재 최소 차이: min_difference = 7.

---

두 번째 반복 (i = 1)

• 끊는 전선: [2, 3].
• 그래프 구성:
• graph = { 1: [3], 2: [], 3: [1, 4], 4: [3, 5, 6, 7], 5: [4], 6: [4], 7: [4, 8, 9], 8: [7], 9: [7] }

 

BFS 탐색

첫 번째 전력망 크기 (size_one):

1. BFS 시작: node = 1.
2. 탐색 순서:
   •   queue = deque([1]).
   •   1 → 3 → 4 → 5, 6, 7 → 8, 9.
3. size_one = 8 (노드 {1, 3, 4, 5, 6, 7, 8, 9}).

두 번째 전력망 크기 (size_two):

• {size_two} = n - {size_one} = 9 - 8 = 1.

크기 차이 계산:

• ∣8−1=7.
• 현재 최소 차이 유지: min_difference = 7.

---

세 번째 반복 (i = 2)

• 끊는 전선: [3, 4].
• 그래프 구성:
• graph = { 1: [3], 2: [3], 3: [1, 2], 4: [5, 6, 7], 5: [4], 6: [4], 7: [4, 8, 9], 8: [7], 9: [7] }

 

BFS 탐색

첫 번째 전력망 크기 (size_one):

1. BFS 시작: node = 1.
2. 탐색 순서:
   •   queue = deque([1]).
   •   1 → 3 → 2.
3. size_one = 3 (노드 {1, 3, 2}).

두 번째 전력망 크기 (size_two):

• size_two= n - size_one= 9 - 3 = 6.

크기 차이 계산:

• ∣3−6∣=3.
• 현재 최소 차이 갱신: min_difference = 3.

---

남은 반복

위와 같은 과정을 각 전선을 끊으며 반복합니다.

---

최종 결과

최소 차이:

• 모든 경우를 탐색한 후, min_difference = 3.

 

출력

print(solution(n, wires))  # 3

---

DFS?

def dfs(node, graph, visited):
    """DFS를 사용하여 한 전력망의 크기를 계산"""
    visited[node] = True
    count = 1  # 현재 노드를 포함한 송전탑 개수
    
    for neighbor in graph[node]:
        if not visited[neighbor]:
            count += dfs(neighbor, graph, visited)
    
    return count

def solution(n, wires):
    min_difference = float('inf')

    # 모든 전선을 하나씩 끊어보며 탐색
    for i in range(len(wires)):
        # 그래프 생성
        graph = {i: [] for i in range(1, n + 1)}
        visited = [False] * (n + 1)

        # i번째 전선을 제외한 나머지 연결 정보 추가
        for j, (v1, v2) in enumerate(wires):
            if i == j:  # i번째 전선을 끊는다.
                continue
            graph[v1].append(v2)
            graph[v2].append(v1)

        # DFS로 첫 번째 전력망 크기 탐색
        size_one = dfs(1, graph, visited)
        size_two = n - size_one

        # 두 전력망 크기의 차이를 계산하여 최소값 갱신
        min_difference = min(min_difference, abs(size_one - size_two))

    return min_difference