https://school.programmers.co.kr/learn/courses/30/lessons/86971
문제 파악
wires 라는 2차원 배열을 입력받는다.
[[1,2],[2,3]] 이라면 1번 노드와 2번 노드가, 2번 노드와 3번 노드가 서로 연결되어 있다는 뜻이다.
예를 들어
wires = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
이면 위 그림처럼 트리가 만들어진다.
이 중 간선 하나를 끊었을 때,
연결된 두 덩이(트리)의 노드 개수 차이가 가장 작은 값을 구하는 문제이다.
예를 들어 3-4 혹은 4-7을 끊으면
노드 개수가 각각 6개와 3개로 나뉘므로,
|6 - 3| = 3을 return 해야 한다.
해결 아이디어
문제에서 트리임이 보장되어 있다.
트리는 “사이클이 없는 연결 그래프(Acyclic Connected Graph)”이므로
모든 노드는 반드시 하나의 연결망으로 이어져 있다.
따라서 모든 간선을 하나씩 끊어보는 완전탐색으로 접근할 수 있다.
트리의 간선 수는 n-1이므로 n이 커도 충분히 가능하다.
- 간선 하나를 끊는다.
- 남은 간선들로 연결된 한쪽 덩이의 노드 개수를 센다.
- 한 쪽의 연결 개수 구하면 나머지 연결된 덩이의 개수는
n - 한쪽의 연결개수이 다.
=> 두 덩이의 연결 개수 차이 = |(n - 한쪽의 연결 개수) - 한쪽의 연결 개수| 가 된다.
= |n - 2 * 한쪽의 연결 개수|
- 모든 간선에 대해 최소 차이를 구한다.
내가 실패했던 부분
처음에는 mass_1, mass_2 두 리스트를 만들어서
각각 True/False로 표시하며 두 덩이를 따로 세려 했다.
하지만 한쪽만 완성해도 나머지는 n - size로 계산할 수 있다는 점을 놓쳤다.
또, “간선 하나를 뺐을 때 어떻게 덩이를 구성할까?”를 떠올리지 못했다.
인접 리스트를 만들 생각만 하다 보니, 간선을 그대로 훑으며 집합을 확장하는 방식을 생각하지 못했던 것.
결국 덩이를 확장하는 흐름(while changed)을 이해한 뒤에서야 감이 잡혔다.
해답 및 풀이
def solution(n, wires):
answer = n # 가능한 최댓값
for i in range(len(wires)):
sub = wires[i+1:] + wires[:i] # i번째 간선 제거
# i번째 간선을 제외한 나머지 간선들을 sub에 저장
# 예: wires = [[1,2],[2,3],[3,4]]이고 i=1이면 sub = [[3,4],[1,2]]
# 예외 처리: n=2인 경우 (간선이 하나뿐)
# 한 간선을 끊으면 1과 1로 나뉘므로 바로 0 반환
if not sub:
return 0
one_side_root = set(sub[0]) # 한쪽 덩이의 시작점, 부터 확장할 것임
changed = True # 연결 확장이 일어났는지를 표시할 플래그
while changed:
changed = False # 이번 턴에서 확장 없으면 종료 예정
# 제거한 간선을 제외한 그래프를 돌면서
for a, b in sub:
# 현재 덩이(one_side_root)와 연결된 간선을 찾아 one_side_root를 확장한다.
# a나 b 중 하나라도 이미 덩이에 속해 있다면 연결됨
if a in one_side_root or b in one_side_root:
# 업데이트 전 덩이 크기를 기록해 두고
before = len(one_side_root)
# 해당 간선의 양 끝 노드(a, b)를 덩이에 합친다(집합 확장)
one_side_root.update((a, b))
# 크기가 늘어났다면(= 새 노드가 추가되었다면) 이번 라운드에서 확장 발생
# → 다음 while 라운드도 한 번 더 돌게끔 changed True 변경
if len(one_side_root) != before:
changed = True
# 한쪽 덩이 크기 = len(one_side_root)
# 다른 쪽 덩이 크기 = n - len(one_side_root)
# 두 덩이 크기 차이 = |(n - len(one_side_root)) - len(one_side_root)|
# = |n - 2 * len(one_side_root)|
answer = min(answer, abs(n - 2 * len(one_side_root)))
return answer
인접리스트 없이도 set.update() 로
“현재 덩이에 닿는 간선”을 하나씩 흡수하며
연결된 모든 노드를 모을 수 있었다.
while changed 루프는
“더 이상 연결될 노드가 없을 때까지” 확장하는
일종의 BFS/DFS 역할을 한다.
