알고리즘 - DFS와 BFS

개요

---

코테 준비를 시작했는데 너무 부족함을 느끼고 있다. 나오는 문제는 막힘없이 풀 수 있는 정도가 되고 싶다. 왜 이렇게 해야 하는가에 대한 이유는 다음 글을 읽어보길 바란다. 도움이 되는 내용도 많다!

 

https://yozm.wishket.com/magazine/detail/2755/

개발자를 위한 실전 ‘코딩테스트’ 준비 팁 | 요즘IT

 

그래서 나는 이전에 강의로 배웠던 내용을 다시 공부하거나 부족한 부분을 채우려고 한다. 처음은 DFS와 BFS로 스타트를 끊고자 한다.

 

설명은 백준의 1260번 문제를 기준으로 할 것이다.

문제의 예제와 결과

 

 

 

DFS 깊이 우선 탐색

---

 

우선 DFS와 BFS에 대한 개념은 이전 글에서도 다루었다. 따라서 여기서 해당 개념을 세세히 설명하지 않고, 프로그래밍 언어로 구현하는 과정과 중요한 부분에 대해 설명하겠다.

 

먼저 요약하자면, DFS는 완전탐색 기법 중 하나다. 루트를 기점으로 하나의 분기를 끝까지 탐색하고 다른 분기를 탐색하는 식이다. 재귀와 스택으로 구현이 가능하다.

 

Java로 구현한 코드를 보자.

 

• 재귀로 구현한 DFS

public class Main {

	static StringBuilder sb = new StringBuilder();
	static boolean[] check;
	static int[][] arr;
	
	static int node, line, start;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		node = Integer.parseInt(st.nextToken());
		line = Integer.parseInt(st.nextToken());
		start= Integer.parseInt(st.nextToken());
		
		arr = new int[node+1][node+1];
		check = new boolean[node+1];
		
       		 // 양방향 간선을 표시하기 위한 초기화 작업
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	
		}
			dfs(start);
            bw.write(sb.toString());
            bw.flush();
            bw.close();
		}
	public static void dfs(int start) {
			check[start] = true; //1
			sb.append(start + " "); //2
			for(int i = 0 ; i <= node ; i++) { //3
				if(arr[start][i] == 1 && !check[i]) //4
					dfs(i); //5
			}
	}
}

 

코드를 한줄한줄 뜯어보자. (아래 리스트 번호는 dfs 함수 코드 오른쪽의 번호와 같다.)

1. 해당 정점이 탐색되었음을 나타낸다. (false -> true)
2. 해당 정점을 StringBuilder에 넣는다.
3. 깊이 우선 탐색을 위해 정점의 갯수만큼 반복한다.
4. 해당 정점 start와 정점 i 사이에 간선이 존재하고, 아직 탐색되지 않았다면 함수를 재귀적으로 호출한다.

여기서 가장 중요한 부분은 4번이다. DFS를 실행하는 재귀함수가 종료되는 조건이 명확히 명시돼 있다. 재귀적으로 처리하기 위한 조건이 충족된 셈이다. 이 조건을 만족하지 않으면 Stackoverflow가 발생될 것이다. 따라서 재귀함수를 작성할 땐 명확하고 적절한 조건이 필요하다.

 

• 스택으로 구현한 DFS

public static void dfs(int start) {
        Stack<Integer> stack = new Stack<>(); // 1
        stack.push(start); //2
        check[start] = true;
        
        while (!stack.isEmpty()) { //3
            int current = stack.pop(); //4
            sb.append(current + " ");
            
            for (int i = 0; i <= node; i++) {
                if (arr[current][i] == 1 && !check[i]) { //5
                    stack.push(i);
                    check[i] = true;
                }
            }
        
	}

 

1. Stack 저장소를 구현한다. 이 Stack은 정수 타입의 데이터만 받을 수 있다.
2. 시작 정점의 데이터를 삽입한다.
3. stack이 전부 비워질 때까지 아래 코드들을 동작시킨다.
4. Stack은 맨 마지막 데이터를 반환한다.
5. 정점의 수만큼 반복하여 간선이 있고 탐색되지 않은 정점을 stack에 저장한다. 이 이후의 로직은 똑같다.

확실히 재귀로 구현한 코드가 짧고 가독성이 좋다. 그래프의 모든 경로를 탐색하거나 각 경로마다 특징을 정해둬야 한다면 DFS가 좋다.

 

BFS 넓이 우선 탐색

---

 

BFS는 루트를 기점으로 인접한 노드(또는 요소, 분기)를 먼저 탐색하여 가장 멀리 떨어진 노드를 나중에 탐색하는 기법이다. Queue를 이용해 구현할 수 있다.

 

public class Main {

	static StringBuilder sb = new StringBuilder();
	static boolean[] check;
	static int[][] arr;
	
	static int node, line, start;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		node = Integer.parseInt(st.nextToken());
		line = Integer.parseInt(st.nextToken());
		start= Integer.parseInt(st.nextToken());
		
		arr = new int[node+1][node+1];
		check = new boolean[node+1];
		
       		 // 양방향 간선을 표시하기 위한 초기화 작업
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	
		}
			bfs(start);
            bw.write(sb.toString());
            bw.flush();
            bw.close();
		}
	static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>(); // 1
        q.offer(start); 
        check[start] = true;

        while (!q.isEmpty()) {
            int p = q.poll(); // 2
            sb.append(p).append(' ');
            for (int i = 1; i <= node; i++) {
                if (arr[p][i] == 1 && !check[i]) { // 3
                    q.offer(i);
                    check[i] = true;
                }
            }
        }
    }
}

 

1. Queue를 구현한다. Queue는 FIFO 방식의 자료구조다.
2. Queue에 삽입된 값(p)을 가져온다.
3. 노드의 수만큼 반복하며 조건이 충족된 노드를 Queue에 삽입한다.

BFS는 두 노드 사이의 최단 경로를 찾고자 할 때 사용한다. 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않을 때도 사용한다.