[코딩인터뷰 완전정복] 4.1 노드 사이의 경로

Q : 방향 그래프가 주어졌을 때 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성하라.

 

 

그래프 노드 갯수만큼의 원소를 가진 배열을 사용한다. 이를 연결 배열이라고 하겠다. 연결 배열은 0으로 초기화 시켜준다.

주어진 2개의 노드는 각각 A,B노드라고 한다.

 

1. A노드를 시작점으로 삼고 연결된 노드들을 탐색한다.

2. 탐색한 노드에 해당하는 연결 배열의 원소를 1로 바꿔준다. 만약 탐색하려는 노드가 이미 1이면 리턴한다.

3. B노드에 해당하는 연결 배열의 원소가 1이 된다면 A에서 B로가는 경로가 존재한다.

   연결되어 있지 않다면 시작 노드를 B노드로 바꿔 다시한다.

4. A,B 두 노드에서 모두 연결되어 있지 않다면, A와 B사이의 경로는 존재하지 않는다.