DanStory

DFS / BFS 탐색 알고리즘 코드로 구현하기

알고리즘은 형태로 구현합니다.

1. Queue/Stack 에 있는 노드를 꺼내 출력한다.
2. 방금 꺼낸 노드의 자식들을 Queue/Stack에 add/push 한다.
3. Queue/Stack이 비어있지 않다면 1번으로 이동

1. 행렬 구현

아래와 같잉 이진트리를 행렬로 표현하면 그림 1의 표의 내용과 같습니다.

2. 코드 구현

그림 1의 내용을 하나씩 탐색하는 코드는 아래와 같습니다.

package java_BFS_DFS_basic;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Matrics_DFS_BFS {
	static Stack<Integer> s = new Stack<Integer>();
	static Queue<Integer> q = new LinkedList<Integer>();
	
	public static void bfs(int start, int[][] map, boolean[] visitied) {
		
		// Queue가 빌때까지 반복
		while(!q.isEmpty()) {
			start = q.peek();
			System.out.print((q.poll()+1)+" ");
			// 1. 자식 노드를 모두 Queue에 삽입
			for(int i=0; i<map.length; i++) {
				if(map[start][i] == 1 && !visitied[i]) { q.add(i); visitied[i] = true;}
			}
		}
	}
	
	public static void dfs(int start, int[][] map, boolean[] visitied) {
		//범위 넘어가면 return
		if(start < 0 || start > map.length) {return ;}
		
		// 1. 출력한다.
		System.out.print((s.pop()+1) +" ");
		
		// 2. 자식 노드를 모두 Stack에 삽입
		for(int i=0; i<map.length; i++) {
			if(map[start][i] == 1 && !visitied[i]) { s.push(i); visitied[i] = true;}
		}
		
		// 3. Stack이 빌때까지 반복
		if(!s.isEmpty()) {
			dfs(s.peek(),map,visitied);
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[][] map = {{1,1,1,0,0,0,0},{1,1,0,1,1,0,0},{1,0,1,0,0,1,1},{0,1,0,1,0,0,0},{0,1,0,0,1,0,0},{0,0,1,0,0,1,0},{0,0,1,0,0,0,1}};
		boolean[] visitied; 
		
		System.out.println("DFS 시작");
		visitied = new boolean[map.length];
		s.push(0);
		visitied[0] = true;
		dfs(0,map,visitied);
		System.out.println();
		System.out.println();
		
		System.out.println("BFS 시작");
		visitied = new boolean[map.length];
		q.add(0);
		visitied[0] = true;
		bfs(0,map,visitied);
	}

}

3. 결과 값

이렇게 해서 BFS DFS 탐색은 끝!

진수를 변환하는 알고리즘을 사용하면 간단하게 풀리는 문제들이 있습니다.

그래서 진수 변환하는 방법을 정리해보도록 하죠

1. 10진수 -> 2진수 변환

public void DecimalTobinary(int num) {
		StringBuffer sb = new StringBuffer(); // 거꾸로 출력하기 위한 버퍼 생성
		String answer="";
		while(num>0) {
			answer += num%2;
			num = num/2;
		}
		sb.append(answer); // 버퍼에 answer 저장하고
		System.out.println(sb.reverse()); // 거꾸로 출력하기
	}

2. 10진수 -> 8진수 변환

public void DecimalToOctal(int num) {
		StringBuffer sb = new StringBuffer();
		String answer="";
		while(num>0) {
			answer += num%8;  //8로 나눈 나머지 저장
			num = num/8; // 8 나누기
		}
		sb.append(answer);
		System.out.println(sb.reverse());
	}

이제 특징이 보이나여??
10진수 -> N진수로 변환하고 싶으면 원하는 숫자를 0이 될때까지 N으로 나눈 나머지를 출력하면 된다는 것!
(단, N은 1< N < 10을 만족하는 정수)

// 2 -> 10
// 8 -> 10
// 16 -> 10 , 10 -> 16 등등 모두 정리하기

3. 

피보나치수열을 알면 1분컷 모르면 난이도 헬이 되는 문제들이 많죠

피보나치 수열 문제는 구현이 어렵지 않습니다.
이 문제를 피보나치로 풀 수 있느냐 아니냐를 판단할 수 있는 능력이 더욱 중요할 것 같습니다.

시작!

1. 피보나치 수열

피보나치는 f(n) = f(n-1) + f(n-2) 라는 공식을 갖는 수열입니다.

f(1) = 1, f(2) = 1 이라고 가정하게 되면 수열은 아래와 같이 진행됩니다.

1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> 34 -> 55 -> 89 -> 144 .....

대표적으로 타일링 문제가 피보나치 수열을 사용하는 문제 중 하나죠.

피보나치를 구현하는 방법은 다양합니다만 오늘 다룰 방식은 1)재귀함수 방식, 2)for문을 이용한 방식
이렇게 2가지로 구현하여 정리 해 볼 예정입니다.

2. 재귀함수를 이용하여 피보나치 수열 구현하기

public int fibo_Recursive(int num) {
		//1,1,2,3,5,8,13,21,34,55,89,143 ...
		if(num == 1) {return 1;}
		else if(num == 2) {return 1;}
		else
			return fibo_Recursive(num-2) + fibo_Recursive(num-1);
	}

코드는 간단합니다.

그럼 피포나치 수열 중 6번째 수를 구하는 과정을 보도록 하겠습니다. (1, 1, 2, 3, 5, 8 ...)

6번째 값을 구하는 과정을 보면 위 그림과 같이  f(5) -> f(4) -> f(3) -> f(2),f(1) 순서로 함수를 호출하며 값을 더해 갑니다.

그런데 이 경우 구현은 쉽지만 재귀함수 특성상 메모리를 많이 사용하기 때문에 코딩테스트에서 사용하기엔 적합하지 않습니다.

그래서 두 번째 방법 반복문을 이용하여 피보나치를 구현하는 것 입니다.

2. 반복문을 이용하여 피보나치 수열 구현하기

코드를 먼저 보도록 하겠습니다.

public int fobo_loop(int num) {
		int cur = 1;  // 현재 값
		int next = 1; // 다음 값
		int answer = 0; // 합을 저장할 변수
		
		for(int i=1; i<=num; i++) {
			cur = next;
			next = answer;
			answer = next + cur;
		}
		return answer;
	}

for문으로 구현할 경우
1) 현재 값을 저장할 변수 cur 다음 값을 저장할 next, 그리고 두개의 합을 저장할 변수 answer을 생성하고
2) 첫째항부터 원하는 위치까지 하나씩 더하는 과정을 반복 합니다.

6번째 항을 구하는 과정을 그림으로 봅시다.

그림에서 보듯이 첫째 항 : cur = 1,  둘째 항 : next = 2로 두고, 이 두개를 더한 값을 answer에 저장합니다.
처음에 6번째 수를 구하고자 하였으니 6번을 반복하게 되면 원하는 값인 8이 출력되게 됩니다.

반복문으로 구현하게 되면 기대 되는 시간 복잡도는 O(n)이 되기 때문에  재귀함수에 비해 효율적으로 사용할 수 있어 코딩테스트를 할때 사용하기 편리합니다.

이상!

코딩 테스트를 준비할때 알아두면 시험볼때 편리 할 코드들을 정리하겠습니다.

1.  행렬의 순환

여기서 포스팅하려는 행렬의 순환은 N x M 행렬이 주어지고,
아래 그림과 같이 한 방향으로 순환을 하는 코드를 말합니다.

그림으로 예를 보자면

1) 코드를 한 번 실행하면 아래 그림과 같이 (1,2)에 있는 동그라미가 (1,3)으로 이동

2) 한번 더 실행하면 (1,3)에 있는 동그라미가 (2,3)으로 이동

3) 이것을 반복하면 행렬의 가장자리를 순환하게 됩니다.

이와 같은 행렬의 순환 코드를 정리 해보도록 하겠습니다.

2. 가장자리를 한칸 씩 이동하기

여기서 구현해 볼 코드는 그림 1 -> 그림 2 에서 볼때 처럼 (1,2)에 있는 동그라미를 삭제하고
(1,3)에 입력 해서 한번만 수행하는 것이 아닌,
아예 한번 실행하면 (1,1) 부터 가장자리만 한 칸씩 이동하도록 구현해 보겠습니다!!

그림으로 보자면 아래와 같습니다.

1) 한바퀴 돌면 아래 그림과 같이 가장자리를 1칸씩 이동합니다.

2) 한바퀴 더 돌면 아래 그림과 같아집니다.

3. 코드로 구현하기

이제 코드로 구현해보겠습니다.

package codingTest_concept;

public class Matrix_circulation {
	
	public void circulation(String[][] matrix) {
		
		int start_h = 0;
		int start_w = 0;
		String temp_1 = matrix[start_h][start_w];
		String temp_2 = "";
		
		//오른쪽 이동
		while(start_w != matrix.length-1) {
			temp_2 = matrix[start_h][start_w+1];
			matrix[start_h][start_w+1] = temp_1;
			temp_1 = temp_2;
			start_w = start_w+1;
		}
		//아래로 이동
		while(start_h != matrix.length-1) {
			temp_2 = matrix[start_h+1][start_w];
			matrix[start_h+1][start_w] = temp_1;
			temp_1 = temp_2;
			start_h = start_h+1;
		}
		//왼쪽으로 이동
		while(start_w != 0) {
			temp_2 = matrix[start_h][start_w-1];
			matrix[start_h][start_w-1] = temp_1;
			temp_1 = temp_2;
			start_w = start_w-1;
		}
		//위로 이동
		while(start_h != 0) {
			temp_2 = matrix[start_h-1][start_w];
			matrix[start_h-1][start_w] = temp_1;
			temp_1 = temp_2;
			start_h = start_h-1;
		}
		
		//출력
		for(int i=0; i<matrix.length; i++) {
			for(int j = 0; j<matrix[i].length; j++ ) {
				System.out.print(matrix[i][j]+" ");
			}
			System.out.println();
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Matrix_circulation m = new Matrix_circulation();
		
		String[][] matrix = {{"A","B","C"},{"H"," ","D"},{"G","F","E"}};
		
		m.circulation(matrix);
		System.out.println();
		m.circulation(matrix);
		

	}

}

4. 코드 설명

코드가 어떻게 돌아가는건지 그림으로 정리해보져

1. 첫번째로 temp_1, tmep_2를 생성한 후, temp_1에는 시작 위치의 값을 저장합니다.
그리고 오른쪽 이동 while문으로 진입합니다. 그리고 temp_2에 그 오른쪽 위치의 값을 저장합니다.

2. 그 다음 temp_1에 저장된 값을 오른쪽 위치에 저장하고, 현재 위치를 한칸 이동합니다.
(여기까지가 while문 오른쪽 이동 1바퀴 입니다.)

3. 다시 1번 부터 반복하게 됩니다.
1)temp_2에 현위치 기준 오른쪽 값을 저장하고,
2)오른쪽 위치에 temp_1에 저장된 값을 삽입합니다.
3) temp_1에 temp_2 값을 저장합니다.
4)그리고 현재 위치를 오른쪽으로 +1 하여 이동시킵니다.
5) 현재 위치가 행렬크기와 같아짐으로 while문을 빠져나옵니다.

- while문 아래쪽
오른쪽 이동이 완료되었으니, 아래쪽으로 이동 while문을 시작합니다.
1) temp_2에 현 위치 기준 아래쪽 위치의 값을 저장합니다.
2) temp_1에 저장되어있던 값을 아래쪽 위치에 저장합니다.

3) 그리고 아래 그림과 같이 현재 위치를 아래로 한 칸 이동합니다.
(이렇게 하면 아래쪽 while문 한바퀴를 돌게 됩니다.)

그림 9, 그림 10 과정을 아래쪽 위치가 행렬의 h 크기와 동일해질때까지 반복합니다.

이렇게 되면 현재 위치와 행렬의 h값과 동일해짐으로 while문을 빠져나옵니다.

그 다음은 왼쪽 이동 while로 진입하게 됩니다.

왼쪽 이동은 오른쪽 이동 반대로, 위쪽 이동은 아래쪽 이동 반대로 진행되기에 그림은 생략하겠습니다.
(귀찮은거 아님)

왼쪽이동 while을 끝내고 위쪽이동 while을 끝내면 아래 그림과 같이 마무리가 됩니다!

이렇게 메서드를 실행하면 한바퀴를 돌게 되는 것이죠!

움직이는 미로 탈출이나, 광고판 시뮬레이션 문제를 풀게될때, 이용하면 좋을 것 같아 정리해보았습니다.

while문의 순서를 바꾸면 반 시계방향으로 돌릴 수 있고, 한번 실행 시 2칸씩 이동한다는 조건이 있으면, 위 메서드를 2번 실행시키면 됩니다.

물론, 효율성 문제를 따지는 문제라면 다른 방식을(?) 찾아봐야겠지만요.