일반적으로 탐색할 때랑 조금 다른 상황입니다.
노드가 예를 들어
0: []
1: [2, 3]
2: [1]
3: [1, 4, 5]
4: [3]
5: [3]
요런식으로 연결되있다고 했을 때 visted를 만들어서 한 번만 탐색하느게 아니라 중복되서 방문해야할때 어떻게 구현해야 할까요?
예를들면, 기본 전제로 모든 노드를 방문하고 싶은데 추가로 2번 노드와 4번노드를 먼저 방문하고 싶습니다.
1
/ \
2 3
/ \
4 5
그렇게 되잇을때 1 -> <2> -> 1 -> 3 -> <4> -> 3 -> 5
이렇게 방문하게 끔 하고싶어요.
근데 일반적인 그래프 탐색을 구현할때는 visted를 써서 재방문하지 않게 구현하고 무한 반복을 방지하잖아요?
그런데 이경우는 재방문이 필요합니다.
그런고로 어떻게 해야할지 모르겠어서.. 조언 부탁드립니다.
Dfs 찾아봐
DFS랑 백트래킹 찾아봐
재귀함수를 쓰면 됩니다 예를 들어 현재 노드가 3이면 visit[3]=1 로 하고 4 를 호출합니다. 4 에서는 3 으로 가려하지만 visit 이 돼있어 못갑니다. 결국 4는 더 이상 재귀호출을 못하고 return 합니다. return 되면 자동으로 3 으로 돌아옵니다. 글쓴이님이 의도한대로 되는 것이죠
즉 visit 배열을 써야하는건 마찬가지고, 재귀함수를 쓰면 재방문이 아닌, return 되는 것이라고 보면 됩니다. 참고로 글쓴이님이 예시로 든 tree 형태 그래프는 visit 배열이 필요없고, 자신을 호출한, 자신의 직전 노드로만 가지 않게 해도 충분합니다.
노드가 작으면 비트마스킹으로 가능
고맙습니다. 조언 덕분에 풀었습니다