from collections import defaultdict
def dfs(cur, cnt):
global visited
visited[cur] = True
cnt += 1
for node in graph[cur]:
if not visited[node] and is_connect[cur][node]:
cnt = dfs(node, cnt)
return cnt
def solution(n, wires):
answer = int(1e9)
global visited
global graph
global is_connect
graph = defaultdict(list)
is_connect = [[False] * (n+1) for _ in range(n+1)]
for start, end in wires:
graph[start].append(end)
graph[end].append(start)
is_connect[start][end] = True
is_connect[end][start] = True
for start, end in wires:
visited = [False] * (n+1)
is_connect[start][end] = False
is_connect[end][start] = False
result = abs(dfs(start, 0) - dfs(end, 0))
if answer > result:
answer = result
is_connect[start][end] = True
is_connect[end][start] = True
return answer
문제 정의
하나의 트리를 둘로 나눈 뒤 노드의 개수의 차가 최소가 되도록 하는 문제이다.
시간 복잡도 계산
완전 탐색이 먼저 가능한지 계산해 봤다.
n이 최대 100이므로 최대 99개의 edge 중 하나를 선택하는 경우의 수는 99이고
그때마다 최대 100개의 노드를 탐색한다면 최대 연산 횟수는 9900이다.
따라서 완전 탐색이 충분히 가능하다.
문제 풀이
연결정보를 하나씩 제거해 보고 제거 지점에서 각각의 트리에 대하여
DFS로 한 번씩 순회하여 노드 수의 차를 계산해 주었다.
예외 사항
문제 조건에 따라 기타 예외 사항은 발생하지 않음 확인.