본문 바로가기

알고리즘

그래프의 최단 경로 찾기

Basic 100 · 49번Lv. 3그래프 탐색(BFS·DFS)

그래프의 최단 경로 찾기

문제 설명

주어진 무방향 그래프에서 두 노드 간의 최단 경로의 길이를 계산하는 함수를 작성해주세요. 그래프는 딕셔너리 형태로 표현되며, 키는 노드를 나타내고 값은 해당 노드에 직접 연결된 이웃 노드들의 리스트입니다.

예를 들어, 노드 0과 노드 3 간의 최단 경로를 찾는 경우, 그래프가 {"0": ["1", "2"], "1": ["0", "3"], "2": ["0"], "3": ["1"]}로 주어진다면, 최단 경로의 길이는 2입니다 (0 -> 1 -> 3).


제한 사항

  • 노드의 수는 1 이상 100 이하입니다.
  • 각 노드는 0부터 시작하는 정수를 문자열로 쓴 이름("0", "1", …)으로 표현됩니다.
  • 노드 사이에 여러 경로가 있을 수 있습니다. 간선에는 방향이 없어 양쪽으로 오갈 수 있습니다.
  • 시작 노드와 목표 노드는 서로 다르고 그래프 안에 반드시 있으며, 둘 사이에는 항상 경로가 있습니다. 경로의 길이는 지나간 간선의 수입니다.
  • 입력 data는 {"graph": 그래프, "start": 시작 노드, "end": 목표 노드} 형태로 주어집니다(입출력 예는 세 값을 나눠 적었습니다).

입출력 예

입력 (그래프, 시작 노드, 목표 노드)반환값 (최단 경로 길이)
{"0": ["1", "2"], "1": ["0", "3"], "2": ["0"], "3": ["1"]}, "0", "3"2
{"0": ["1"], "1": ["0", "2"], "2": ["1"]}, "0", "2"2
{"0": ["1"], "1": ["0"]}, "0", "1"1

입출력 설명

주어진 그래프에서 시작 노드와 목표 노드 간의 최단 경로의 길이를 계산하여 반환합니다.

예시 테스트

#입력기대값
1{"graph": {"0": ["1", "2"], "1": ["0", "3"], "2": ["0"], "3": ["1"]}, "start": "0", "end": "3"}2
2{"graph": {"0": ["1"], "1": ["0", "2"], "2": ["1"]}, "start": "0", "end": "2"}2
3{"graph": {"0": ["1"], "1": ["0"]}, "start": "0", "end": "1"}1

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.