[알고리즘] - DFS, BFS

Python으로 구현하는 DFS, BFS와 Java로 구현하는 DFS, BFS는 다소 차이가 있어, 작성해 봅니다.

 

1. DFS(깊이 우선 탐색)

기본적인 완전 탐색 알고리즘으로, 재귀,스택을 이용해서 구현합니다.

DFS의 경우, 탐색 공간이 제한되어 있고, 탐색 공간 내 탐색 목표가 있는지 검사할 때 유용합니다.

 

-  특징

1. 탐색 순서 -> 깊이 우선으로, 현재 상태에서 전이할 수 있는 상태가 있으면 해당 상태로 우선 전이=> 탐색 공간이 제한되어 있지 않으면 적용 힘듦.
2. 최단 경로를 찾지 못함
3. 작은 공간 복잡도 -> 최대 깊이가 H일 때, O(H)의 공간복잡도를 가진다.

- 구현

// Stack을 이용한 DFS 구현

// 방문 검사 배열
boolean[] isVisited = new boolean[N];
Stack<Integer> stack = new Stack<>();

// 초기 상태
stack.add(/* initialState= */ = 0);

// 탐색 진행
while (!stack.isEmpty()) {
	int state = state.pop();

// 중복 검사
	if (isVisited[state]) continue;
    isVisited[state] = true;
    
// 현재 상태 처리
	/* 현재 상태 state 처리 */

// 전이 상태 생성
	for (int next : getNextStates(state)) {
    	// 범위 검사 => continue;
    	// 유효성 검사 => continue;
    	stack.push(next);
    }
}

- 예제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

네트워크 - level 3

import java.util.Stack;

public class Solution {
	private void visitAll(int computer, int[][] computers, boolean[] isVisited) {
    	Stack<Integer> stack = new Stack<>();
        stack.push(computer);
        
        while(!stack.isEmpty()) {
        	int c = stack.pop();
            
            if (isVisited[c]) continue;
            isVisited[c] = true;
            
            for (int next = 0; next < computers[c].length; next++) {
            	if (computers[c][next] == 0) continue;
                stack.push(next);
            }
 		}
	}
    
    public int solution(int n, int[][] computers) {
    	boolean[] isVisited = new boolean[n];
        int answer = 0;
        
        for (int i =0; i < n; i++) {
        	if (isVisited[i]) continue;
            visitAll(i, computers, isVisited);
            answer++;
        }
        
        return answer;
    }
}

 

 

2. BFS (너비 우선 탐색)

기본적인 완전 탐색 알고리즘으로, 큐를 이용해서 구현합니다.

최단 거리, 최단 시간 등 목표 상태에 도달할 수 있는 가장 빠른 경로를 탐색하는데 사용합니다.

 

- 특징

1. 탐색 순서 -> 초기 상태에서 가까운 상태부터 탐색 => 최단 경로임을 알 수 있음
2. 탐색 공간의 길이 제한 없음
3. 높은 공간 복잡도

- 구현

// Queue를 이용한 BFS 구현

boolean[] isVisited = new boolean[N];

Queue<Integer> queue = new LinkedList<>();
queue.add(/* initialState = */ 0);
isVisited[/* initialState = */ 0] = true;

while(!queue.isEmpty()) {
	int state = queue.poll();
    
    /* 현재 상태 처리 */
    
    for (int next : getNextStates(state)) {
    	// 범위 검사
        // 유효성 검사
        // 중복 검사
        // 방문처리
        queue.add(next);

- 예제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

import java.util.*;

public class Solution {
	private static class State {
    	public final int x;
        public final int y;
        public final int step;
        
        private State(int x, int y, int step) {
        	this.x = x;
            this.y = y;
            this.step = step;
            }
        }

	private static final int[] dx = {0, 1, 0, -1}
    private static final int[] dy = {-1, 0, 1, 0}
    
    public int solution(int[][] maps) {
    	boolean[][] isVisited = new boolean[maps.length][maps[0].length]
        
        Queue<State> queue = new LinkedList<>();
        queue.add(new State(0,0,1);
        isVisited[0][0] = true;
        
        while (!queue.isEmpty()) {
        	State state = queue.poll();
            
            if (state.y == maps.length - 1 && state.x == maps[state.y].length - 1) {
            	return state.step;
            }
            
            for (int d = 0; d < 4; d++) {
            	int nx = state.x + dx[d];
                int ny = state.y + dy[d];
                
                if (ny < 0 || ny >= maps.length || nx < 0 || nx > maps[ny].length) {
                	continue;
                }
                
                if (maps[ny][nx] != 1) {
                	continue;
                }
                
                if (isVisited[ny][nx]) {
                	continue;
                }
                
                isVisited[ny][nx] = true;
                queue.add(new State(nx,ny,state.step + 1);
                }
			}
		
        return -1;
	}
}

 

- 참고 : 취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략 : 자바 편