[자료 구조] 그래프 : DFS, BFS

 

DFS와 BFS는 그래프 탐색 알고리즘으로, 그래프의 노드를 탐색하는 방법입니다.

 

시간 복잡도 인접 리스트 : O(V + E), 인접 행렬 : O(V^2)

DFS(깊이 우선 탐색)는 그래프의 시작 노드에서부터 시작하여 한 분기(branch)씩 내려가면서 그래프를 탐색하는 방법입니다. 이때 각 분기마다 하나의 노드를 선택하여 방문하며, 더 이상 방문할 노드가 없을 때 이전 분기로 돌아가서 다른 노드를 방문합니다. 이러한 과정을 반복하여 그래프 전체를 탐색합니다. DFS는 스택(Stack) 자료구조를 이용하여 구현할 수 있습니다.

BFS(너비 우선 탐색)는 그래프의 시작 노드에서부터 시작하여 인접한 모든 노드들을 먼저 탐색한 후에, 그 다음으로 인접한 노드들을 탐색하는 방법입니다. 이때 큐(Queue) 자료구조를 이용하여 구현할 수 있습니다.

 

DFS 

 

Stack 혹은 재귀함수(Recursion)으로 구현된다.

경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행
모든 노드를 방문하는 경우에 이 방법을 사용한다.

 

 

스택으로 구현

boolean[] visited = new boolean[node.size()];

//간선 정보 graph에 업데이트


Stack<Node> stack = new Stack<>();

stack.push(new Node(0,0)); //임의의 노드 삽입
visited[0] = true;

while(!stack.isEmpty()){
	Node cur = stack.pop();
    
    // for문으로 인접 노드들을이 방문하지 않았을 경우 스택에 넣고 방문 처리
    
    for{
    	if(!visited[cur.to]){
        	stack.push(cur);
            visited[cur.to] = true;
         } 
    }
}

재귀적으로 구현

boolean[] visited = new boolean[node.size()];

public void dfs(Node node){

	visited[node.to] = true; //방문 처리
    
    //for문으로 인접한 노드 찾은 후 방문한 적이 없으면 dfs 수행
    for() {
    
    	if(!visited[node.to]){
        	dfs(node);        
        } 
    }
}

public static void main(String[] args) {
		dfs(0);
}

 

BFS 

 

Root Node 혹은 다른 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법이다.
Queue를 사용해서 구현한다.

 

 

queue 구현 

 

public static void BFS(Graph graph, int v, boolean[] visited)
    {
        // BFS를 수행하기 위한 Queue 생성
        Queue<Integer> queue = new ArrayDeque<>();
 
        // 소스 정점을 발견된 것으로 표시
        visited[v] = true;
 
        // 소스 정점을 큐에 넣습니다.
        queue.add(v);
 
        // Queue가 비어있을 때까지 루프
        while (!queue.isEmpty())
        {
            v = queue.poll();
            System.out.print(v + " ");
 
            // 모든 에지(v, u)에 대해 수행
            for (int u: graph.adjList.get(v))
            {
                if (!visited[u])
                {
                    // 발견된 것으로 표시하고 대기열에 넣습니다.
                    visited[u] = true;
                    queue.add(u);
                }
            }
        }
  	}

재귀적인 BFS 

	public static void recursiveBFS(Graph graph, Queue<Integer> queue,
									boolean[] visited)
	{
		if (queue.isEmpty()) {
			return;
		}

		// dequeue front node and print it
		int v = queue.poll();
		System.out.print(v + " ");

		// do for every edge (v, u)
		for (int u: graph.adjList.get(v))
		{
			if (!visited[u])
			{
				// mark it as discovered and enqueue it
				visited[u] = true;
				queue.add(u);
			}
		}

		recursiveBFS(graph, queue, visited);
	}

 

 DFS, BFS 이해 하기

 

 

0-1 BFS란? -> 다익스트라 대신 최단 경로를 찾을 때 쓸 수 있는 알고리즘

BFS는 BFS인데 특수한 환경에서 작동할 수 있는 BFS이다. 그 특수한 환경이 뭐냐고?  
0-1을 보면 무엇인지 추측할 수 있다. 0-1 BFS는 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 풀 수 있게 된다.

아니 최단 경로는 다익스트라가 베스트가 아니란 말인가? 적어도 이 그래프에서는 아니다.  

보편적으로 사용하는 다익스트라 알고리즘의 시간 복잡도가 O(ElogE)  혹은 O(ElogV)
인데 0-1 BFS를 사용하면 단지 O(V+E) 의 선형 시간 복잡도로 문제를 해결할 수 있기 때문이다.

0-1 BFS의 동작

왜 0-1 BFS가 O(V+E) 에 동작할 수 있을까?  

이는 BFS에서 노드를 관리하기 위해 큐를 사용하는 대신 덱(deque)을 사용하여 실현할 수 있다.  
0-1 BFS는 다음 과정에 따라 최단 경로를 찾게 된다.  

1. 덱의 front에서 현재 노드를 꺼낸다
2. 연결된 인접 노드를 살펴본다.
3. 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다.
4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.
5. 덱에서 더 이상 꺼낼 노드가 없을 때까지 위 과정을 반복한다.

O(V+E)  증명
위 과정을 생각해보자.  

0-1 BFS를 수행하면 가중치가 1인 간선을 0번 거쳐간 노드 -> 가중치가 1인 간선을 1번 거쳐간 노드 -> .... -> 가중치가 1인 간선을 E번 거쳐간 노드

이런 식으로 비용이 적은 경로부터 탐색을 하게 되기 때문에 특정 간선을 2번 이상 지나가는 경우는 없다. O(E)
똑같이 모든 정점도 2번 이상 경유하는 경우가 없으므로 덱 크기는 최대 |V|
이다. O(V)  

따라서 0-1 BFS는 O(V)+O(E)=O(V+E) 의 시간 복잡도를 가지게 된다.

 

 

아래 문제들은 0-1 BFS에 이해하고 풀어볼 문제들이다. 좀 더 이해가 된 후에 풀어보면 좋을 듯하다.

 

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {

    public static int[] check;

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))) {
            String[] s = reader.readLine().split(" ");
            int n = Integer.parseInt(s[0]);
            int k = Integer.parseInt(s[1]);
            check = new int[100001];
            Arrays.fill(check, -1);

            bfs(n, k);
            writer.write(check[k] + "");
        }
    }

    public static void bfs(int n, int k) {
        LinkedList<Integer> queue = new LinkedList<>(); // deque
        queue.offer(n);
        check[n] = 0;

        while (!queue.isEmpty()) {
            int position = queue.poll();

            if (position == k) {
                return;
            }

            if (position * 2 <= 100000 && check[position * 2] == -1) {
                queue.addFirst(position * 2); // 높은 우선순위
                check[position * 2] = check[position];
            }

            if (position > 0 && check[position - 1] == -1) {
                queue.offer(position - 1);
                check[position - 1] = check[position] + 1;
            }

            if (position < 100000 && check[position + 1] == -1) {
                queue.offer(position + 1);
                check[position + 1] = check[position] + 1;
            }
        }
    }

}

코드 출처 : https://velog.io/@nmrhtn7898/ps-0-1-BFS

 

https://www.acmicpc.net/problem/2423

2423번: 전구를 켜라

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

출처 : https://foameraserblue.tistory.com/188

출처 : https://devuna.tistory.com/32