#052 · BFS/DFS중간BFS / 그래프 최단 경로

최단 인맥 거리

문제

사내 메신저에서 N명의 직원이 있고, 일부 직원들끼리 친구 관계로 연결되어 있습니다. 친구의 친구에게 메시지를 전달할 수 있을 때, start번 직원이 end번 직원에게 메시지를 전달하려면 최소 몇 단계를 거쳐야 하는지 반환하세요.

직접 친구이면 1, 불가능하면 -1을 반환하세요.

n=5, edges=[[1,2],[2,3],[3,4],[4,5],[1,3]], start=1, end=5
→ 3 (1→3→4→5)

시간 복잡도 목표: O(N + E)

예시 1: 1→3→4→5 → 3단계

입력: n = 5, edges = [[1,2],[2,3],[3,4],[4,5],[1,3]], start = 1, end = 5

출력: 3

예시 2: 연결 안 됨 → -1

입력: n = 4, edges = [[1,2],[3,4]], start = 1, end = 4

출력: -1

예시 3: 직접 친구 → 1

입력: n = 2, edges = [[1,2]], start = 1, end = 2

출력: 1

예시 4: 직접 연결 있음 → 1

입력: n = 3, edges = [[1,2],[2,3],[1,3]], start = 1, end = 3

출력: 1

예시 5: 1→2→4→5→6 → 4단계

입력: n = 6, edges = [[1,2],[1,3],[2,4],[3,4],[4,5],[5,6]], start = 1, end = 6

출력: 4

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.