[알고리즘/java] 그래프 최단거리(BFS 인접리스트)

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

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

 

 

 

 

문제 :  다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선 수를 출력하라.

입력 : 

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부턴 M줄에 걸쳐 연결정보가 주어진다.

 

입력예시 :

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로 푼다 생각)

또한 그래프는 인접행렬 / 인접리스트의 형태로 구현할 수 있지만 이 문제에서는 인접리스트를 이용한다.

그리고 1번 정점에서 각 정점으로 가는 최소 간선 수를 저장하기 위해 int 배열 dis를 생성한다.

ex) dis[3] = 1번 정점에서 3번까지 가는 최소 간선 수.

 

dis

0

1

1

 

: 정점 1에서 한 번만에 갈 수 있는 정점은 3, 4다.

그래서 dis[3] dis[4]에 1을 넣는다.

( 현재 큐: 3, 4)

 

현재 정점에서 다음 정점으로 가는 최소간선수는 이전 정점의 최소 간선수 + 1이다.

즉,  d[nv] = d[v] + 1이다.

 

 

 

 

dis

0

1

1

2

2

 

: 큐에서 poll한 정점 3에서 한 번만에 갈 수 있는 정점은 4가 있지만 이미 방문했으므로 패스.

그 다음 poll한 정점 4에서 한 번만에 갈 수 있는 정점은 5, 6이다.

그래서 dis[5] dis[6]에 2를 넣는다.

( 현재 큐: 5 6)

 

 

 

 

dis

0

3

1

1

2

2

 

: 큐에서 poll한 정점 5에서 한 번만에 갈 수 있는 정점이 없으므로 패스.

그 다음 poll한 정점 6에서 한 번만에 갈 수 있는 정점은 2, 5이다. (5는 이미 방문했으므로 패스)

그래서 dis[2]에 3를 넣는다.

( 현재 큐:  )

 

큐에 남아있는 정점이 없으므로 BFS를 종료한다.

 

채워진 dis 배열을 출력하면 1번부터 각 정점으로 이동하는 최소 간선 수를 알 수 있다.

 

 

 

 

< 그래프 최단거리 (BFS) 전체 코드 >

public class Main {

	private static int n, m;
	private static int[] dis;
	private static ArrayList<ArrayList<Integer>> graph;
	private static int[] ch;

	public static void BFS(int v) {

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

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

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		graph = new ArrayList<ArrayList<Integer>>();
		ch = new int[n + 1];
		dis = new int[n + 1];

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

		// 그래프 인접리스트로 만들기
		for (int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			graph.get(a).add(b);
		}

		BFS(1);

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

	}

}