[프로그래머스]전력망을 둘로 나누기

[46] 전력망을 둘로 나누기

책 구매하기

문제 정보

• 분류: 그래프
• 정답률: 47%
• 권장 시간 복잡도: O(N^2)
• 핵심 키워드: 트리, 간선 제거, 연결 요소 크기, BFS
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/86971

문제를 읽을 때 체크할 포인트

전선을 하나 끊을 때마다 트리가 두 조각으로 나뉜다. 각 전선을 하나씩 제거해 보고, 한쪽 크기를 세면 다른 쪽 크기는 전체에서 빼서 바로 구할 수 있다.

최단 거리나 연결성처럼 칸과 칸, 정점과 정점 사이를 따라가야 하는 문제는 결국 탐색 구조가 핵심이다. 방문 상태를 어떻게 정의하느냐가 정답을 거의 결정한다.

풀이 흐름

1. 전선 목록을 인접 리스트로 만든다.
2. 전선을 하나씩 제거한 상태로 BFS/DFS를 한 번 돌려 연결된 송전탑 수를 센다.
3. 두 그룹 크기 차이의 최솟값을 갱신한다.

구현할 때 놓치기 쉬운 부분

전선을 하나 끊을 때마다 두 전력망의 크기를 다시 세어야 한다. 간선을 제거한 뒤 남은 그래프에서 연결된 노드 수를 정확히 세는 흐름을 놓치면 차이 계산이 어긋난다.

파이썬 정답 코드

from collections import deque

def solution(n, wires):
  # 전선 목록을 인접 리스트로 만든다.
  graph = [[] for _ in range(n + 1)]
  # 전선을 하나씩 제거한 상태로 BFS/DFS를 한 번 돌려 연결된 송전탑 수를 센다.
  for a, b in wires:
    graph[a].append(b)
    graph[b].append(a)

  def count_nodes(block_a, block_b):
    visited = [False] * (n + 1)
    q = deque([1])
    visited[1] = True
    count = 0

    while q:
      cur = q.popleft()
      count += 1
      for nxt in graph[cur]:
        if (cur == block_a and nxt == block_b) or (cur == block_b and nxt == block_a):
          continue
        if not visited[nxt]:
          visited[nxt] = True
          q.append(nxt)

    return count

  answer = n
  # 두 그룹 크기 차이의 최솟값을 갱신한다.
  for a, b in wires:
    one_side = count_nodes(a, b)
    other_side = n - one_side
    answer = min(answer, abs(one_side - other_side))

  return answer

시간 복잡도

N은 송전탑 수이다.

기준 원소마다 다른 원소를 다시 보거나, N×N 형태의 연결 관계를 직접 확인하는 구조이다. 그래서 N이 한 번 더 곱해진 O(N^2)로 정리된다.

따라서 시간 복잡도는 O(N^2)이다.