프로그래머스 고득점kit 전력망을 둘로 나누기 | Python
🔎 문제 설명
💚 Level 2
- 난이도 ★★☆☆ - 그래프탐색 DFS - Union-Find
두 가지 접근으로 풀이할 수 있다. 각각의 풀이법은 아래에 설명과 함께 올려놓았다!
💻 내 코드
1️⃣ DFS를 이용한 코드
끊는 전선 1개를 어떻게 처리해줄지만 안다면 기본적인 BFS로 간단하게 풀리는 문제이다. 나는 그래프 tree 에서 해당 전선을 뺐다가 다시 넣어주는 방식으로 진행하였다.
answer는 최댓값이 n이므로 n으로 초기화해줘도 된다.
from collections import deque
def solution(n, wires):
tree = [[] for _ in range(n+1)]
for wire in wires:
x, y = wire
tree[x].append(y)
tree[y].append(x)
def bfs(now):
visited = [0] * (n+1)
queue = deque([now])
visited[now] = 1
cnt = 1
while queue:
x = queue.popleft()
for node in tree[x]:
if not visited[node]:
queue.append(node)
visited[node] = 1
cnt += 1
return cnt
answer = 1e9
for wire in wires:
a, b = wire
tree[a].remove(b)
tree[b].remove(a)
answer = min(answer,abs(bfs(a)-bfs(b)))
tree[a].append(b)
tree[b].append(a)
return answer
2️⃣ Union Find를 이용한 코드
끊는 전선 1개를 정했다면 각각의 트리의 루트 노드가 2개 나오게 된다. 이 방법을 이용해서 방법을 찾는다.
이번 문제를 통해 Union Find로 부모 노드 찾는 방법을 알았다. 더 연습해서 자유롭게 사용할 수 있도록 해야겠다.
import copy
def solution(n, wires):
parent = [x for x in range(n+1)]
def find_parent(parent, x):
if parent[x]!=x:
return find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
answer = 1e9
for i in range(len(wires)):
parent_copy = copy.deepcopy(parent)
for idx, (a, b) in enumerate(wires):
if i==idx:
continue
union_parent(parent_copy, a, b)
x, y = wires[i]
for a, b in wires:
parent_copy[a] = find_parent(parent_copy, a)
parent_copy[b] = find_parent(parent_copy, b)
answer = min(abs(parent_copy.count(parent_copy[x])-parent_copy.count(parent_copy[y])), answer)
return answer
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).