깊이 우선 탐색법(with. kotlin)

이런 그래프가 있다 가정해보자(발편집 ㅈㅅ)

 

이 그래프를 깊이 우선으로 찍으려고 하면 어떻게 해야할까?

애초에 깊이 우선이란 무엇인가? 한번 딥하게 끝까지 갔다가 다시 돌아오는걸 뜻한다.

이걸 일단 말로 풀어보자.

 

1번 노드부터 돈다. 1번 노드에는 2 4 5번이 연결되어있다.

일단 5번부터 가보자. 5번에는 8번이 연결되어있다.

8번을 가보자. 8번은 6번과 연결되어 있다. 

6번을 가보자. 6번은 3번과 연결되어 있다.

3번을 가보자. 3번은 2번과 연결되어 있다.

2번은 1 5 번이 연결되어있다. 그런데 1 5번은 먼저 탐색한 전적이 있지 않은가? 그럼 돌아간다? 어디까지? 노드가 갈라지는 지점까지 ^-^ ..

2번은 방문한 전적이 있다. 그럼 2번도 빼버리고 다시 돌아가 1번 노드로 다시 돌아간다.

4번은 7번과 연결되어 있다. 7번은 아무도 연결되어있지 않기 때문에 분기점인 1로 돌아간다.

이런 식으로 노드를 방문하게 되면 결과는

[1, 5, 8, 6, 3, 2, 4, 7]

의 순서로 돌게 된다

 

이를 스택으로 보자

1			초기 1노드 방문.
4	2	5	1과 연결된 4, 2, 5 방문
4	2	8	5노드로 이동. 5와 연결된 8 방문
4	2	6	8노드로 이동. 8과 연결된 6 방문
4	2	3	6노드로 이동. 6과 연결된 3 방문
4	2		3노드로 이동. 탐색한 적 있는 2 추가하지 않음.
4			2노드로 이동. 탐색한적 있는 1, 5 추가하지 않음
7			마지막 노드.

 

 

이를 코드로 보면..

	val graph = listOf(listOf<Int>(), listOf(1, 4, 5), listOf(3, 5), listOf(6), listOf(7), listOf(), listOf(8), listOf(), listOf(5))
	val visited = Array(computer + 1) { false }
    val stack = Stack<Int>()
    stack.push(1)
        computerVisited[1] = true
        
        while (!stack.empty()) {
            println(stack)
            val nodeIndex = stack.pop()
            graphp[nodeIndex].forEach {
                val destination = it.filter { it != nodeIndex }[0]
                if(!visited[destination]) {
                    stack.push(destination)
                    visited[destination] = true
                }
            }
        }