문제를 풀다보면 가장 많이 마주할 수 있는 문제가 DFS, BFS 문제라고 할 수 있을 정도다.

관련해서 한 번 정리하면서 되새겨보고자 한다.

DFS

DFS는 깊이 우선 탐색이며, 그래프에서 들어갈 수 있는 깊은 부분까지 우선적으로 탐색하는 알고리즘을 말한다.

DFS는 각 장점에 숫자가 있고 a 부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 하는 경우에 사용하면 좋다.

재귀함수나 스택을 사용해서 구현하는데, 여기서는 둘 다 알아보도록 한다.

재귀

재귀의 알고리즘은 다음과 같다.

1. 방문한 노드에 대해서 우선 방문했다는 것을 체크한다. (보통 boolean 배열로 false -> true로 한다.)
2. 다음 탐색할 깊이를 늘리고 동일한 함수를 호출한다.
3. 탐색이 끝나면, 방문했음을 다시 초기화 한다.

public void dfs(int[] graph, int depth, boolean[] visited){
	if(depth == numbers.length){
    	// 탐색을 다 했다면 하고 싶은 로직을 추가하자.
    }
    
    for(int i = 0; i < numbers.length; i ++){
    	if(!visited[i]){
            visited[i] = true;
   			dfs(numbers, depth + 1, visited);
    		visited[i] = false;
        }
    }
}

스택

스택을 이용한 것 역시 비슷하다.

1. 방문한 노드를 스택에 삽입하고, 방문했다는 것에 대해서 체크를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 해당 노드를 스택에 넣고 방문처리를 한다.
3. 만약 방문하지 않은 인접한 노드가 없다면 스택에서 최상위 노드를 pop한다.
4. 위의 과정을 더이상 방문할 수 있는 노드가 없을때까지 반복한다.

public void dfs(int[] graph, int depth, boolean[] visited){
	visited[depth] = true;
    Stack<Integer> stack = new Stack<>();
    stack.push(graph[depth]); // 시작 노드 stack에 삽입

	while(!stack.isEmpty()){
    	int n = stack.peek(); // 현재 노드 확인
        boolean flag = false; // 인접 노드 존재 여부
        
        for(int node : graph){
        	if(!visited[node]){
            	stack.push(node);
                visited[node] = true;
                flag = true;
                break;
            }
        }
        
        if(!flag) { // 방문하지 않은 노드가 하나도 없다면?
        	stack.pop();
        }
   }
}

코드로 봤을땐 재귀를 사용하는게 깔끔하고 좋긴하지만 머릿속에서 재귀에 대해서 고민이 좀 필요할 것 같다.

관련 문제 풀이

프로그래머스-lv2-피로도

---

BFS

BFS는 넓이 우선탐색이며, 그래프에서 일단 근접해있는 모든 같은 깊이의 노드를 탐색하고 그 다음에 그 다음으로 멀리 떨어져있는 노드들을 방문하는 알고리즘이다.

보통은 두 노드 사이의 최단 경로를 찾거나, 경로를 찾고 싶을 때 해당 방법을 사용한다

보통 BFS 알고리즘을 구현할때는 Queue를 사용한다.

큐

큐를 이용해서 구현할때 알고리즘의 흐름은 다음과 같다.

1. 큐에 첫번째 방문한 노드를 넣은 뒤, 방문 처리를 한다.
2. 첫번째 방문한 노드와 가까운 노드를 큐에 넣고 방문 처리를 한다.
3. 큐에서 순서대로 노드를 꺼내면서 인접하였지만 방문하지 않은 노드가 있는지 확인한다.
4. 있다면 큐에 넣고, 방문처리한다. 없다면 다시 큐에서 노드를 하나 더 꺼내고 반복한다.
5. 위의 과정을 큐가 빌 때까지 반복하고, 큐가 비었다면 종료한다.

void BFS(int s) {
		boolean visited[] = new boolean[V]; // 각 노드이 방문 여부를 저장하기 위해
		LinkedList<Integer> queue = new LinkedList<Integer>();
		
		visited[s] = true;
		queue.add(s);
		
		while (queue.size() != 0) {
			// 방문한 노드를 큐에서 추출하고 값을 출력
			s = queue.poll();
			System.out.println(s + " ");
			
			// 방문한 노드와 인접한 모든 노드를 가져온다.
			Itertor<Integer> i = adj[s].listIterator();
			while (i.hasNext()) {
				int n = i.next();
				// 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입
				if (!visited[n]) {
					visited[n] = true;
					queue.add();
				}
			}
		}
	}
}

관련 문제 풀이

프로그래머스-lv2-게임-맵-최단-거리