자바 DFS
스택으로 구현하기
JAVA 코드
static boolean dfs(int a) {
boolean [] visited = new boolean [isCity];
Stack<Integer> stack = new Stack<>();
stack.push(a);
while(!stack.empty()) {
int curr = stack.pop();
if(visited[curr]) continue;
visited[curr] = true;
for(int next = 0; next < isCity; ++next) {
if(!visited[next] && map[curr][next]!=0)
stack.push(next);
}
}
}
그림으로 확인하기
static boolean dfs(int a) {
boolean [] visited = new boolean [isCity];
Stack<Integer> stack = new Stack<>();
stack.push(a);
while(!stack.empty()) {
int curr = stack.pop();
if(visited[curr]) continue;
visited[curr] = true;
for(int next = 0; next < isCity; ++next) {
if(!visited[next] && map[curr][next]!=0)
stack.push(next);
}
}
}
세팅
dfs(0)으로 시작하면..
-
Stack.push(0)
-
While문 시작
2-1. 현재 stack을 pop한다.
2-2. (조건)방문한적이 있는지 확인한다.
2-3. 0은 방문 되었음을 표시한다
-
For문 시작
3-1. 방문한적이 없고 && 간선이 이어져 있다면
3-2. stack에 1을 추가한다.
3-3. stack 2는 추가되지않는다.
다시 2번으로 돌아간다.
2-1로 돌아가 1을 pop한다
2-3로 돌아가 1이 방문되었음을 표시한다.
3번으로 돌아가 0,1을 지나, (방문한적이 있다.)
방문하지 않고 && 1-2로 간선이 이어져있는 2를 stack에 대입한다
Author And Source
이 문제에 관하여(자바 DFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bongsuyeon/자바-DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)