코딩테스트 DFS/BFS

코딩테스트 DFS/BFS

 

탐색(Search)

 

• 많은 양의 데이터 중 원하는 데이터를 찾는 과정
• 대표적 그래프 탐색 알고리즘 : DFS, BFS

 

 

스택

 

• LIFO(Last-In First-Out), 선입후출, 후입선출
• 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조
• 입구와 출구가 동일한 형태로 스택 시각화 가능

 

 

큐

 

• FIFO(First-In First-Out), 선입선출, 후입후출
• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능

 

 

재귀 함수(Recursive Function)

 

• 자기 자신을 다시 호출하는 함수

public static void main(String[] args){
	recursive();
}
public static void recursive(){
	System.out.println("반복합니다");
	recursive();
}

• 재귀 함수를 문제풀이에 사용 시 재귀 함수의 종료 조건 반드시 명시
• 종료 조건을 제대로 명시하지 않으면 함수 무한 호출
• 보통 코딩테스트에서는 재귀 함수보다 반복문이 유리

 

 

팩토리얼 구현

 

• n! = 1 * 2 * 3 * ··· * (n-1) * n
• 0! = 1, 1! = 1 

public static void main(String[] args) {
	Factorial f=new Factorial();
	System.out.println("재귀적으로 구현 = "+f.recursive(3));
	System.out.println("반복적으로 구현 = "+f.repeated(3));
}
public int recursive(int n) {
	if(n<2) return 1;
	return n*recursive(n-1);
}
public int repeated(int n) {
	int sum=1;
	for(int i=2;i<=n;i++) sum*=i;
	return sum;
}
/* 출력결과 
재귀적으로 구현 = 6
반복적으로 구현 = 6
*/

 

 

DFS(Depth-First Search)

 

• 깊이 우선 탐색
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조나 재귀 함수 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
4. 2, 3번 과정 반복 수행

//1
public static void main(String[] args) {
	int[][] graph={{},{2,3,8},{1,7},{1,4,5},{3,5},{3,4},{7},{2,6,8},{1,7}};
	boolean[] visited=new boolean[9];
	dfs1(graph, 1, visited);
}
public static void dfs1(int[][] graph, int v,boolean[] visited) {
	visited[v]=true;
	System.out.printf("%d ",v);
	for(int i:graph[v]) {
		if(!visited[i]) dfs1(graph,i,visited);
	}
}
/* 출력결과
1 2 7 6 8 3 4 5 
실행시간 : 0.016
*/
//2
public static boolean[] visited=new boolean[9];
public static ArrayList<ArrayList<Integer>> graph=new ArrayList<ArrayList<Integer>>();
public static void main(String[] args) {
	graph.add(0,new ArrayList<Integer>());
	graph.add(1,new ArrayList<Integer>(Arrays.asList(2,3,8)));
	graph.add(2,new ArrayList<Integer>(Arrays.asList(1,7)));
	graph.add(3,new ArrayList<Integer>(Arrays.asList(1,4,5)));
	graph.add(4,new ArrayList<Integer>(Arrays.asList(3,5)));
	graph.add(5,new ArrayList<Integer>(Arrays.asList(3,4)));
	graph.add(6,new ArrayList<Integer>(Arrays.asList(7)));
	graph.add(7,new ArrayList<Integer>(Arrays.asList(2,6,8)));
	graph.add(8,new ArrayList<Integer>(Arrays.asList(1,7)));
	dfs2(1);
}
public static void dfs2(int x) {
	visited[x]=true;
	System.out.print(x+" ");
	for(int i=0;i<graph.get(x).size();i++) {
		int y=graph.get(x).get(i);
		if(!visited[y])dfs2(y);
	}
}
/* 출력결과
1 2 7 6 8 3 4 5 
실행시간 : 0.001
*/

 

 

BFS(Breadth-First Search)

 

• 너비 우선 탐색
• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번 과정 반복 수행

//1
public static void main(String[] args) {
	int[][] graph={{},{2,3,8},{1,7},{1,4,5},{3,5},{3,4},{7},{2,6,8},{1,7}};
	boolean[] visited=new boolean[9];
	bfs1(graph, 1, visited);
}
public static void bfs1(int[][] graph, int v,boolean[] visited) {
	Queue<Integer> queue=new LinkedList<Integer>();
	queue.add(v);
	visited[v]=true;
	while(queue.peek() != null) {
		v=queue.poll();
		System.out.printf("%d ",v);
		for(int i:graph[v]) {
			if(!visited[i]) {
				queue.add(i);
				visited[i]=true;
			}
		}
	}
}
/* 출력결과
1 2 3 8 7 4 5 6 
실행시간 : 0.018
*/
//2
public static boolean[] visited=new boolean[9];
public static ArrayList<ArrayList<Integer>> graph=new ArrayList<ArrayList<Integer>>();
public static void main(String[] args) {
	long a1=System.currentTimeMillis();
	graph.add(0,new ArrayList<Integer>());
	graph.add(1,new ArrayList<Integer>(Arrays.asList(2,3,8)));
	graph.add(2,new ArrayList<Integer>(Arrays.asList(1,7)));
	graph.add(3,new ArrayList<Integer>(Arrays.asList(1,4,5)));
	graph.add(4,new ArrayList<Integer>(Arrays.asList(3,5)));
	graph.add(5,new ArrayList<Integer>(Arrays.asList(3,4)));
	graph.add(6,new ArrayList<Integer>(Arrays.asList(7)));
	graph.add(7,new ArrayList<Integer>(Arrays.asList(2,6,8)));
	graph.add(8,new ArrayList<Integer>(Arrays.asList(1,7)));
	bfs2(1);
}
public static void bfs2(int start) {
	Queue<Integer> queue=new LinkedList<Integer>();
	queue.offer(start);
	visited[start]=true;
	while(!queue.isEmpty()) {
		int x=queue.poll();
		System.out.print(x+" ");
		for(int i=0;i<graph.get(x).size();i++) {
			int y=graph.get(x).get(i);
			if(!visited[y]) {
				queue.offer(y);
				visited[y]=true;
			}
		}
	}
}
/* 출력결과
1 2 3 8 7 4 5 6
실행시간 : 0.001
*/