[코딩테스트]DFS

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

1. DFS(깊이 우선 탐색)이란 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 입니다.

 

2. DFS 코드 : 방문 우선순위는 숫자가 작은 순으로

 

*방문 우선순위에 따라 탐색이 달라질 수 있습니다.*

 

import java.util.*;

class Node{
	int var;
	boolean visited;
	LinkedList<Node> adjacent;
	
	Node(int v){
		var = v;
		visited = false;
		adjacent = new LinkedList<Node>();
	}
}

public class MyDFS2 {
	
	static LinkedList<Node> abc = new LinkedList<Node>();
	//Stack을 이용한 dfs구현
	public static void dfs(int num) {
		Stack<Node> a = new Stack<Node>();
		a.push(abc.get(num));
		while(!a.empty()) {
			Node temp = a.pop();
			if(!temp.visited) {
				System.out.print(temp.var+" ");
				temp.visited = true;
			}
			for(int i=temp.adjacent.size()-1;i>=0;i--) {
				Node y = temp.adjacent.get(i);
				if(!y.visited) {
					a.push(y);
				}
			}
		}
	}
	
	//재귀함수를 이용한 dfs구현
	public static void dfs_jg(int num) {
		Node av = abc.get(num);
		av.visited = true;
		System.out.print(" "+ num);
		//abb.push(abc.get(num));
		for(int j=0;j<av.adjacent.size();j++) {
			if(!(av.adjacent.get(j).visited)) {
				dfs_jg(av.adjacent.get(j).var);
			}
		}
	}
	
	public static void main(String[] args) {
		for(int i=0;i<9;i++) {
			abc.add(new Node(i));
		}
		
		abc.get(1).adjacent.add(abc.get(2));
		abc.get(1).adjacent.add(abc.get(3));
		abc.get(1).adjacent.add(abc.get(8));
		
		abc.get(2).adjacent.add(abc.get(1));
		abc.get(2).adjacent.add(abc.get(7));
		
		abc.get(3).adjacent.add(abc.get(1));
		abc.get(3).adjacent.add(abc.get(4));
		abc.get(3).adjacent.add(abc.get(5));
		
		abc.get(4).adjacent.add(abc.get(3));
		abc.get(4).adjacent.add(abc.get(5));
		
		abc.get(5).adjacent.add(abc.get(3));
		abc.get(5).adjacent.add(abc.get(4));
		
		abc.get(6).adjacent.add(abc.get(7));
		
		abc.get(7).adjacent.add(abc.get(2));
		abc.get(7).adjacent.add(abc.get(6));
		abc.get(7).adjacent.add(abc.get(8));
		
		abc.get(8).adjacent.add(abc.get(1));
		abc.get(8).adjacent.add(abc.get(7));
		
		dfs_jg(1);
	}

}

 

 DFS를 Stack과 재귀함수를 통해 구현해보았다. 차이점은 재귀함수가 Stack을 통한 구현보다 쉽고 간결하게 코드를 작성할 수 있지만, 시간복잡도가 Stack을 통한 구현보다 높다고 합니다.

 

 개선점을 찾자면 코드를 작성하면서 변수를 정하고 작성하는게 아니라 아무렇게나 작성하여서 코드가 지저분해 보입니다. 따라서 해당 변수나 함수이름을 누구나 알아볼 수 있게 짜는 연습을 하면 좋을 것 같다고 생각합니다.

 

출력결과 : 1 2 7 6 8 3 4 5