[인터돌™] 공부 해보자!! 열심히~~~

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();		
		}
	}
}

 

이 글을 공유합시다

facebook twitter googleplus kakaoTalk kakaostory naver band

본문과 관련 있는 내용으로 댓글을 남겨주시면 감사하겠습니다.

비밀글모드