재귀함수, 스택을 이용한 DFS 코드 (자바)
2020. 6. 15. 23:46
반응형
DFS는 재귀함수를 이용할수도 있고 스택을 이용할 수도 있다.
작성한 두개의 코드는 재귀함수를 이용한 것이고, 트리는 값을 코드에서 셋팅, 배열은 실행시 입력 해야 한다.
재귀함수를 이용한 트리 DFS
import java.util.ArrayList;
/* 재귀함수를 이용한 DFS 트리 전체 탐색을 방문 순서대로 출력
1
2 3
4 5 6 7
*/
public class StudyDFSTreeBacktrack {
static ArrayList<Integer>[] G = new ArrayList[8];
static boolean[] isVisited = new boolean[8];
static void dfs(int now) {
System.out.println(now);
// 자식 노드를 돌면서 또다른 자식이 있다면 재귀함수 호출
int next;
for (int i = 0 ; i<G[now].size() ; i++) {
next = G[now].get(i);
if (isVisited[next] == false) {
isVisited[next] = true;
dfs(next);
}
}
}
public static void main(String[] args) {
// 정점 리스트 객체 생성
for (int i =1 ; i < G.length ; i++) {
G[i] = new ArrayList<Integer>();
}
// 자식노드 추가
G[1].add(2);
G[1].add(3);
G[2].add(4);
G[2].add(5);
G[3].add(6);
G[3].add(7);
int now = 1;
isVisited[now] = true;
dfs(1);
}
}
재귀함수를 이용한 배열 DFS
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/* 재귀함수를 이용한 DFS 배열 전체 탐색을 방문 순서대로 출력
입력 값
1
7 6
SOOOOO
OXXOOO
OOOXOO
OOOOOO
XOOOXX
XOOOOO
OOXXOX
*/
public class StudyDFSDimBacktrack {
static int M = 0; // 맵의 가로 사이즈
static int N = 0; // 맵의 세로 사이즈
static boolean[][] isVisited;
static String[][] map; // 지도
static void dfs (int[] now) {
System.out.println("NOW : " + Arrays.toString(now));
// 범위를 벗어나지 않는가? 이미 방문 했는가? 입력값이 X 가 아닌가? 를 체크 후 탐색
// 순서는 ↓ ← ↑ → 로 한다
int[] next = new int[2];
// 아래
next[0] = now[0]+1;
next[1] = now[1];
// System.out.println("아래 NOW : " + Arrays.toString(now) + " NEXT : " + Arrays.toString(next));
if ((next[0] <=M) && (isVisited[next[0]][next[1]] == false) && !(map[next[0]][next[1]] == null) && !(map[next[0]][next[1]].equals("X")) ) {
isVisited[next[0]][next[1]] = true;
dfs (next);
}
// 왼쪽
next[0] = now[0];
next[1] = now[1]-1;
// System.out.println("왼쪽 NOW : " + Arrays.toString(now) + " NEXT : " + Arrays.toString(next));
// System.out.println("왼쪽 isVisited : " + isVisited[next[0]][next[1]]);
if ((next[1] > 0) && (isVisited[next[0]][next[1]] == false) && !(map[next[0]][next[1]] == null) && !(map[next[0]][next[1]].equals("X")) ) {
isVisited[next[0]][next[1]] = true;
dfs (next);
}
// 위
next[0] = now[0]-1;
next[1] = now[1];
// System.out.println("위쪽 NOW : " + Arrays.toString(now) + " NEXT : " + Arrays.toString(next));
if ((next[0] > 0) && (isVisited[next[0]][next[1]] == false) && !(map[next[0]][next[1]] == null) && !(map[next[0]][next[1]].equals("X")) ) {
isVisited[next[0]][next[1]] = true;
dfs (next);
}
// 오른쪽
next[0] = now[0];
next[1] = now[1]+1;
// System.out.println("오른 NOW : " + Arrays.toString(now) + " NEXT : " + Arrays.toString(next));
if ((next[1] <= N) && (isVisited[next[0]][next[1]] == false) && !(map[next[0]][next[1]] == null) && !(map[next[0]][next[1]].equals("X")) ) {
isVisited[next[0]][next[1]] = true;
dfs (next);
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int test_case = Integer.parseInt(st.nextToken()); // 문제 번호. 여기선 고려해서 코딩하지 않았음
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new String[M+1][N+1];
// map 에 입력받은 지도 입력
for (int i=1 ; i<= M ; i++) {
String[] temp1 = br.readLine().split("");
for (int j=0 ; j<temp1.length ; j++) {
map[i][j+1] = temp1[j];
}
}
// System.out.println(Arrays.deepToString(map));
// 탐색 구문 시작
isVisited = new boolean[M+1][N+1];
int[] now = new int[2]; // 인덱스 0 : 가로, 인덱스 1: 세로
now[0] = 1; // 시작점 설정 (가로)
now[1] = 1; // 시작점 설정 (세로)
isVisited[now[0]][now[1]] = true;
dfs (now);
}
}
스택을 이용한 트리 DFS
import java.util.ArrayList;
import java.util.Stack;
/*
* 1
* 2 3
* 4 5 6 7
*
* 요런 모양의 트리를 스택을 이용해서 DFS 탐색을 한다.
*/
public class DFS {
public static void main(String[] args) {
ArrayList<Integer>[] G = new ArrayList[8]; // 트리를 저장할 동적 배열
Stack<Integer> stack = new Stack<Integer>(); // 탐색을 위한 스택
boolean[] isVisited = new boolean[9]; // 방문 여부를 저장하기 위한 정적 배열
int now, next; // 현재 방문한 노트, 다음 방문할 노드
boolean hasNext; // 다음 노드 방문 여부
for (int i=0; i< G.length ; i++){ // 동적 배열 객체 할당
G[i] = new ArrayList<Integer>();
}
// 동적 배열에 그래프 저장
G[1].add(2);
G[1].add(3);
G[2].add(4);
G[2].add(5);
G[3].add(6);
G[3].add(7);
stack.push(1);
isVisited[1] = true;
while(!stack.isEmpty()){ // 스택이 빌 때까지 무한 반복
now = stack.peek(); // 현재 노드를 스택에서 확인
hasNext = false; // 다음 방문 노드 여부 초기화
System.out.println(now);
for (int i = 0; i < G[now].size() ; i++){ // 현재 노드의 길이만큼 반복
next = G[now].get(i);
// System.out.println("넥스트 : " + next);
if (isVisited[next] == false) {
stack.push(next);
isVisited[next] = true;
hasNext = true;
break;
}
}
if (hasNext == false)
stack.pop();
}
}
}
이 글을 공유합시다
