[www.acmicpc.net/problem/1389]
#풀이- bfs를 이용해서 각각 유저가 다른 유저를 만날 때 거치는 사람의 합을 구하면 된다.
1. bfs에서 현재 큐에 있는 사람과 다음 큐에 있는 사람을 구분해서 거치는 사람 수를 증가시켜야 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | import sys input = lambda: sys.stdin.readline().rstrip() #bfs 알고리즘 def bfs(g,vi,p): #모든 사람 (shallow copy) v=vi[:] #큐 안에 있는 사람과 연결된 사람을 구할때 쓰인다 queue=[p] friend=0 sum=0 while v: next_queue=[] for i in queue: if i in v: v.remove(i) next_queue.extend(g[i]) sum+=friend #기존 큐에 사람이 빠지면 다음 큐를 넣는다 queue=next_queue #다리가 한다리 더 건너진 것이다 friend+=1 return sum a,b=map(int,input().split()) graph={i:set() for i in range(1,a+1)} visit=[i for i in range(1,a+1)] #딕셔너리를 이용해서 연결하기 for i in range(b): c,d=map(int,input().split()) graph[c].add(d) graph[d].add(c) #최소값 5000*5001//2 보다 작다 m=12502500 for i in range(1,a+1): tmp=bfs(graph,visit,i) if tmp < m: m=tmp m_per=i print(m_per) | cs |
댓글 쓰기