자바 알고리즘 깊이우선탐색

Question

안녕하세요. 자바 dfs 공부하면서 코드를 짜봤는데 스택으로 구현하는 메소드와 재귀호출로 구현하는 메소드의 탐색값이 다르게 나와서 이렇게 질문 올립니다. 제가 봤을때 Stack으로 구현한 메소드에서 뭔가 꼬여서 값이 다르게 나오는 것 같은데 어느부분이 잘못된건지 잘 모르겠습니다. 한번 봐주시면 감사하겠습니다.public class DFSExam { public static int[][] graph = {{}, {2,3,8}, {1,7}, {1,4,5}, {3,5}, {3,4}, {7}, {2,6,8}, {1,7}}; public static boolean[] visite = new boolean[9]; //dfs 재귀 public static void dfsRecursive(int v) { visite[v] = true; System.out.print(v + " "); for(int i : graph[v]) { if(!visite[i]) { dfsRecursive(i); } } } //dfs 스택 public static void dfsStack(int v) { Stack stack = new Stack<>(); stack.push(v); visite[v] = true; while(!stack.isEmpty()) { int idx = stack.pop(); System.out.print(idx + " "); for(int i=graph[idx].length-1; i>=0; i--) { int node = graph[idx][i]; if(!visite[node]) { stack.push(node); visite[node] = true; } } } }재귀 탐색 결과 ->1 2 7 6 8 3 4 5스택 탐색 결과 ->1 2 7 6 3 4 5 8

yeori · Accepted Answer

visite[node] &#61; true; 를 체크하는 타이밍이 재귀와 스택이 약간 다릅니다.재귀 버전은 visit이 true가 아니면 메소드 호출해서 들어간 후에 true로 체크하는데,반복문 버전에서는 일단 다 trrue로 체크해놓고 스택에 집어넣어버립니다. node 8의 경우를 보면재귀에서는 1 -> 2 -> 7번 방문했을때 { 2, 6, 8} 에서 8번을 방문하고 true로 체크하는데반복문 버전에서는 다음 노드를 스택에 넣을때 미리 true로 체크해버렸기때문에 스택에서 7번을 꺼낸 후 {8, 6, 2}에 대해 루프를 돌면 8번은 이미 방문했다고 표시되어서 건너뜁니다. 8번은 맨 처음 1번 노드 방문했을때 { 8, 2, 3 } 순서로 집어넣어서 맨 마지막에 들어가 있기때문에 빼낼때도 맨 마지막에 나옵니다.

자바 알고리즘 깊이우선탐색

1개의 답변

Q&A 목록