[Algorithm] DFS와 BFS

Byul·2024년 12월 30일

algorithm

Algorithm

목록 보기

3/4

DFS(깊이우선탐색 : Dreadth-First Search)

루트 노드에서 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 방법이다. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색한다.
어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 검사하지 않으면 무한루프에 빠질 수 있다.
미로를 탐색할 때 해당 분기에서 갈 수 있을 때 까지 가다가 더 못가게 되면 다시 가장 가까운 갈림길로 돌아가는 것과 유사하다.
BFS(너비우선탐색) 보다 간단하지만 검색속도 자체는 느리다.

ex)

이 사진을 보면 알 수 있듯이 루트 노드 1에서 2로 이동하고 해당 분기를 모두 탐색한뒤 5로 이동하고 3으로 이동하는 것을 볼 수 있다.

DFS 예시 구현 코드


	/// dfs, 재귀, 인접 행렬, i 정점부터 시작한다.
    public static void dfs(int i) {		
    	visit[i] = true; // 노드 중복 접근 방지를 위한 방문 체크 배열. (boolean)
    	System.out.print(i + " ");
    	// j는 dfs 배열의 새로운 분기를 뜻한다.(int)
    	for(int j=1; j<n+1; j++) {  			
    		if(map[i][j] == 1 && visit[j] == false) {
        		dfs(j);			
    		}		
    	}	
    }

재귀나 스택을 사용하여 자기 자신을 다시 호출하는 순환 알고리즘이다.

BFS(너비우선탐색 : Bread-First Search)

BFS는 재귀적으로 동작하지 않는다.
BFS 또한 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 검사하지 않으면 무한루프에 빠질 수 있다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용하여 선입선출의 원리로 동작한다.
루트 노드로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 순회 방법이다.
깊게 보단 넓게 탐색한다고 보면 된다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.

ex)

1에서 2로 이동 후에 4나 5로 가는 것이 아니라 인접한 3으로 이동한다.

BFS 예시 코드


	// bfs, q사용, 인접행렬, i 정점부터 시작한다.
	public static void bfs(int i) {
    	Queue<Integer> q = new LinkedList<>();
        q.offer(i);
        visit[i] = true; // 노드 중복 탐색 방지를 위한 방문 체크 배열
        
        while(!q.isEmpty()) {
        	int temp = q.poll();
            System.out.println(temp + " ");
            for(int j=1; j<n+1; j++) {
            	if(map[temp][j] ==1 && visit[j == false]) {
                	q.offer(j);
                    visit[j] = true;
                }
            }
        }
    }