728x90
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
1.90ms
import copy, sys
def solution(n, wires):
answer = sys.maxsize
g=[[] for _ in range(n+1)]
for s,e in wires:
g[s].append(e)
g[e].append(s)
visited=[False]*(n+1)
def BFS(v, e):
del_wire=[[v,e], [e,v]]
queue=[]
visited[v]=True
queue.append(v)
while queue:
now=queue.pop(0)
visited[now]=True
for i in g[now]:
if not visited[i] and [now,i] not in del_wire:
queue.append(i)
for s,e in wires:
visited=[False]*(n+1)
BFS(s, e)
answer = min(answer,abs(n-2*visited[1:].count(True)))
return answer
15.20ms
import copy, sys
def solution(n, wires):
answer = sys.maxsize
g=[[] for _ in range(n+1)]
for s,e in wires:
g[s].append(e)
g[e].append(s)
visited=[False]*(n+1)
def BFS(v, tree):
queue=[]
visited[v]=True
queue.append(v)
while queue:
now=queue.pop(0)
visited[now]=True
for i in tree[now]:
if not visited[i]:
queue.append(i)
for s,e in wires:
visited=[False]*(n+1)
temp=copy.deepcopy(g)
temp[s].remove(e)
temp[e].remove(s)
BFS(s, temp)
answer = min(answer,abs(n-2*visited[1:].count(True)))
return answer
728x90