문제 설명
•
트리 형태로 연결된 송전망에서 전선 하나를 끊어 두 전력망의 송전탑 개수 차이를 최소화하는 문제
예제 입력/출력
n | wires | result |
9 | [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] | 3 |
4 | [[1,2],[2,3],[3,4]] | 0 |
7 | [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] | 1 |
제약 조건
•
•
문제 풀이
•
노드와 간선의 범위
◦
◦
접근1 완전 탐색 + DFS -
풀이 코드
def dfs(node):
global adj_list, visited
# Base Case
if visited[node]:
return 0 # 이미 방문한 경우 노드 수를 0으로 반환
visited[node] = True
cnt = 1 # 현재 노드 포함
# Recursive Case
for adj_node in adj_list[node]:
cnt += dfs(adj_node) # 연결된 노드 수를 재귀적으로 합산
return cnt
def solution(n, wires):
global adj_list, visited, cnt
adj_list = [[] * (n + 1) for _ in range(n + 1)] # 1-index
for a, b in wires:
adj_list[a].append(b)
adj_list[b].append(a)
ans = 100
for a, b in wires:
visited = [0] * (n + 1) # 1-index
adj_list[a].remove(b)
adj_list[b].remove(a)
ans = min(ans, abs(dfs(a) - dfs(b)))
adj_list[a].append(b)
adj_list[b].append(a)
return ans
Python
복사