https://www.acmicpc.net/problem/1389
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
난이도: 실버1
소요시간: 35분
문제를 보자마자 다익스트라를 써야하나 라는 생각이 들었다. 그러나 오늘 풀 주제는 bfs였기에 bfs로 풀었다.
풀고나니 최단거리문제이면서 모든 거리가 1이라면 bfs를 써도된다는 것을 깨달았다. 앞으로 전형적인 최단거리 문제라도 거리가 1이라면 bfs도 고려를 해보아야겠다. 내일은 최단거리로도 한번 풀어보아야겠다.
#16:07 실버1 35분
import sys
from collections import deque
N,M = map(int,sys.stdin.readline().split())
graph=[[] for _ in range(N+1)]
visited = [False]*(N+1)
for i in range(M):
temp1,temp2= map(int,sys.stdin.readline().split())
if temp2 not in graph[temp1]:
graph[temp1].append(temp2)
if temp1 not in graph[temp2]:
graph[temp2].append(temp1)
def bfs(start):
visited = [False] * (N + 1)
deq= deque([[start,0]])
bacon=0
while(deq):
temp=deq.popleft()
q=temp[0]
depth=temp[1]
if visited[q] == True:
continue
bacon += depth
depth+=1
visited[q]=True
for g in graph[q]:
deq.append([g,depth])
return bacon
result=[]
for i in range(1,N+1):
result.append([bfs(i),i])
result.sort(key= lambda x:(x[0],x[1]))
print(result[0][1])
'Problem Solving > BFS' 카테고리의 다른 글
BOJ2606 바이러스 (1) | 2024.03.07 |
---|---|
BOJ11724 연결 요소의 개수 (1) | 2024.03.07 |
BOJ1260 DFS와 BFS (0) | 2024.03.07 |
BOJ1012 유기농 배추 (0) | 2023.03.14 |
미로 탈출 (0) | 2023.01.02 |