[백준] 1389번: 케빈 베이컨의 6단계 법칙 (C++ 풀이)

문제 https://www.acmicpc.net/problem/1389

풀이

BFS로 풀었다.

1번사람에 대해서 다른 연결된 친구들까지의 단계거리(?)를 모두 계산해서 1차원의 dist배열에 저장한다.

dist배열은 -1로 초기화되어있고, 1에서 1로 가는 거리는 0이다.

1번사람에 대해 BFS로 모두 탐색해서 dist배열을 다 채웠으면

dist배열 값을 모두 더해서 제일 작은 값에 대해서만 ans에 따로 저장해둔다.

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1389.cpp

결과