[ 그래프 ] DFS 연습하기 JAVA

문제

그림과 같은 그래프에 대하여 정점의 개수 N, 연결선의 개수 M이 주어지고

그래프에 대한 연결 정보가 주어질 때, 시작 정점 1에서 DFS 방문 경로를 출력하시오.

그래프 정보

 

풀이

DFS를 연습하는 가장 기본적인 문제입니다.

시작 정점 1을 dfs() 함수 실행할 때 입력해준 뒤, Stack을 이용하여

다음 정점과 연결되어 있고 ( map[x][i] == 1 ), 아직 방문하지 않은 정점이 있다면 ( visited[i] == false )

스택에 해당 정점을 넣어주고, 더 이상 방문할 정점이 존재하지 않는다면 pop()을 해주면서

연결되어 있는 모든 정점을 깊이 우선 탐색(Depth First Search)으로 방문하는 문제입니다.

방문한 정점에 대하여 중복 방문하는 경우를 방지하기 위해 visited 배열을 이용하여 방문할 경우 true 값을 이용해

중복처리를 해주었습니다.

 

코드

실행 결과