728x90
😉 아이디어
1. 그래프의 엣지를 제거 후 남은 그래프 중 한 지점으로 뻗치는 엣지 개수 확인
2. _!전체 - 엣지 개수!_가 나머지 👉 이후 문제의 요구사항대로 최소값 산출
😉 풀이
towers = 0
def solution(n, wires):
global towers
graph = [[] for _ in range(n)]
answer = 99_999
# 그래프 그리기
for wire in wires:
x = wire[0] - 1
y = wire[1] - 1
graph[x].append(y)
graph[y].append(x)
# print(f'처음 만들어진 그래프 = {graph}')
for wire in wires:
visited = [0] * n
x = wire[0] - 1
y = wire[1] - 1
# 엣지 제거
graph[x].remove(y)
graph[y].remove(x)
# print(f'특정 엣지가 제거된 그래프 = {graph}')
# 탐색 | 탐색 시작 자체가 타워 1
towers = 1
dfs(x, visited, graph)
second_towers = n - towers
result = abs(towers - second_towers)
answer = min(answer, result)
# 엣지 추가
graph[x].append(y)
graph[y].append(x)
return answer
def dfs(start, visited, graph):
global towers
visited[start] = 1
for node in graph[start]:
if visited[node] == 0:
dfs(node, visited, graph)
towers += 1
✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86971