섹션 7 Recursive, Tree, Graph - 14. 그래프최단거리(BFS)

📌 문제 설명

방향 그래프가 주어졌을 때 1번 정점에서 시작하여 다른 모든 정점까지의 최단 거리(간선 수)를 출력하는 프로그램을 작성한다.

---

📝 입력 & 출력

입력

• 첫 줄: 정점 수 N(1 ≤ N ≤ 20), 간선 수 M
• 다음 M줄: 간선 정보 A B (A → B 방향)

출력

• 1번 정점에서 2번 ~ N번 정점까지의 최소 간선 수를 출력
• 각 정점마다 정점 번호 : 최소 거리 형태로 출력

---

🔹 예제 입력 & 출력

예제 입력

 

6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5

예제 출력

2 : 3  
3 : 1  
4 : 1  
5 : 2  
6 : 2

---

💡 해결 방법

이 문제는 최단 거리를 구하는 문제이므로 BFS를 사용한다.

BFS는 다음과 같은 특징이 있다:

• 루트 노드부터 탐색하면서 가까운 노드부터 먼저 방문
• 큐(Queue)를 사용해 레벨별로 탐색
• 첫 방문한 거리가 최단 거리임이 보장됨
  → 따라서 BFS는 가중치 없는 그래프에서 최단 거리를 구할 때 가장 적절하다

---

💻 코드 구현 (Java)

전체 코드

package partRecursiveTreeGraph;

import java.util.*;

public class Problem14 {
	static int n, m;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] ch, dis;

	public void BFS(int v) {
		Queue<Integer> Q = new LinkedList<>();
		ch[v] = 1;
		dis[v] = 0;
		Q.offer(v);
		while (!Q.isEmpty()) {
			int current = Q.poll();
			for (int next : graph.get(current)) {
				if (ch[next] == 0) {
					ch[next] = 1;
					Q.offer(next);
					dis[next] = dis[current] + 1;
				}
			}
		}
	}

	public static void main(String[] args) {
		Problem14 T = new Problem14();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
		ch = new int[n + 1];
		dis = new int[n + 1];
		for (int i = 0; i < m; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			graph.get(a).add(b);
		}
		T.BFS(1);
		for (int i = 2; i <= n; i++) {
			System.out.println(i + " : " + dis[i]);
		}
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 인접리스트 생성 및 입력 처리

graph = new ArrayList<>();
for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());

• 각 정점의 인접 정점 리스트를 저장

graph.get(a).add(b);

• 방향 그래프이므로 a → b 간선만 추가

---

2️⃣ BFS 함수

Queue<Integer> Q = new LinkedList<>();
ch[v] = 1;
dis[v] = 0;
Q.offer(v);

• 큐 초기화 및 시작 노드 설정
• dis[]: 거리 저장 배열, ch[]: 방문 체크 배열

---

3️⃣ 큐를 사용한 레벨 탐색

while (!Q.isEmpty()) {
	int current = Q.poll();
	for (int next : graph.get(current)) {
		if (ch[next] == 0) {
			ch[next] = 1;
			Q.offer(next);
			dis[next] = dis[current] + 1;
		}
	}
}

• 큐에서 현재 노드를 꺼내고
• 인접한 정점 중 방문하지 않은 노드를
  • 큐에 넣고
  • dis[next] = dis[current] + 1로 거리 갱신

---

4️⃣ 결과 출력

for (int i = 2; i <= n; i++) {
	System.out.println(i + " : " + dis[i]);
}

• 1번 정점에서 각 정점까지의 최단 거리 출력
• 1번 자신은 제외하고 2번부터 출력

---

⏳ 시간 복잡도 분석

• 노드 수: N, 간선 수: M
• BFS는 각 노드를 최대 1번 방문 → O(N)
• 모든 간선을 최대 1번 탐색 → O(M)
• 최종 시간 복잡도: O(N + M)

---

🧠 핵심 정리

• BFS는 가중치 없는 그래프의 최단 거리 문제에 가장 적합
• dis[]: 거리 저장, ch[]: 방문 여부 저장
• 큐에 처음으로 들어온 경로가 최단 거리임이 보장됨
• 시간 복잡도는 O(N + M)으로 효율적

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런