https://school.programmers.co.kr/learn/courses/30/lessons/86971
내 답
"""
해결 방법:
1. 모든 종류를 한 번씩 끊어보고
2. bfs를 이용해 연결되지 않은 노드와 연결된 노드를 분리해서 차이를 구하기
3. 그 차이 중 최소한이 되는 차이 구하기
"""
from collections import defaultdict, deque
graph = defaultdict(list)
def bfs(Dict, visited):
cnt = 0
q = deque()
q.append(1)
visited[1] = True
while q:
n = q.popleft()
if Dict[n]:
for node in Dict[n]:
if not visited[node]:
visited[node]=True
q.append(node)
for i in range(len(visited)):
if visited[i]: cnt+=1
return cnt
def solution(n, wires):
answer = n-2
for wire in wires:
graph[wire[0]].append(wire[1])
graph[wire[1]].append(wire[0])
# print(graph)
for wire in wires:
visited = [False for _ in range(n+1)]
graph[wire[0]].remove(wire[1])
graph[wire[1]].remove(wire[0])
answer = min(abs(n - 2 * bfs(graph, visited)), answer)
graph[wire[0]].append(wire[1])
graph[wire[1]].append(wire[0])
#print("answer is", answer)
return answer
알고리즘은 간단하다.
1. 우선 wires를 dictionay 형태로 만든다. (이때 모든 아이템이 빈 리스트로 초기화되어있는 defaultdict를 이용하면 편하다.)
1-1. print(graph)를 해보면 {1: [3], 3: [1, 2, 4], 2: [3], 4: [3, 5, 6, 7], 5: [4], 6: [4], 7: [4, 8, 9], 8: [7], 9: [7]}
의 모양새가 된다.
2. 다시 1에서 만들어둔 dict에서 wire를 하나씩 터트리며 해당 dict에 대해 bfs를 수행한다.
3. bfs 알고리즘은 다음과 같다. 우선, 1번 노드부터 시작한다. 그리고 큐에 하나씩 넣어가며 해당 노드와 연결되어있는 노드들을 탐방한다. 그리고 방문했으면 visited를 true로 만들어준다.
4. 탐방이 끝난 후 visited가 true인 개수를 센다. 지금 보니까 굳이 이렇게 안해도 될거같다. 그냥 if not visited[node] 문을 들어갈때 cnt를 업그레이드해줘도 됐을거같다. 하지만 난 이 문제를 풀 당시 그 방법이 생각나지 않았다.
5. 그렇게 방문했던 노드들 수를 세서 solution 함수에서 방문한 노드 - 방문 한 적 없는 노드간 차이를 구한다. answer = min(..) 부분이 그 부분이다.
6. 간선들을 하나씩 끊어보면서 answer를 min value로 업데이트한다.
모범 답안
def solution(n, wires):
ans = n
for sub in (wires[i+1:] + wires[:i] for i in range(len(wires))):
s = set(sub[0])
[s.update(v) for _ in sub for v in sub if set(v) & s]
ans = min(ans, abs(2 * len(s) - n))
return ans
시간은 좀 오래 걸리지만 실로 아름다운 코드다.
