DFS(Depth-First Search) + BFS 복습

깊이 우선 탐색(DFS, Depth-First Search)을 알아보기 이전에 그래프에 대한 개념을 이해해야 하므로, 먼저 아래 포스팅을 참고하도록 하자.

그래프와 BFS(Graph & Breadth First Search)

 

1. 깊이 우선 탐색(DFS, Depth-First Search)

 이전 포스트와 '깊이 우선 탐색'이라는 이름에서 알 수 있듯이, '깊이 우선 탐색'은 먼저 한 방향으로 갈 수 있는 경로를 먼저 탐색하는 방식이다. 이는 그래프 탐색의 가장 단순하면서도 고전적인 방법인데, 원리는 간단하다. 현재 정점과 인접한 간선들을 모두 검사하여 아직 방문하지 않은 정점으로 향하는 간선이 있는 경우 해당 간선을 무조건 따라가는 것이다. 더 이상 갈 곳이 없는 정점에 도착했다면 마지막에 따라왔던 간선을 따라 뒤로 돌아가는 방식이다. 이전 포스트에서 사용했던 그래프를 다시 살펴보며 DFS로 수행했을 경우 정점의 방문 순서를 알아보자.

위에서 간단하게 설명한 DFS의 방문 원리를 그래프에 대입했을 때, 실제 방문 순서를 알아보자. 단, 이미지 상 왼쪽 노드를 먼저 방문하는 것으로 한다.

A → G → A → C → D → C → A → B → E → H → I → H → E → B → F 

화살표로 표현하여 다소 복잡한듯 보이지만 처음 방문한 노드는 bold로 표시하였다. D 노드까지 도달하는 경로를 잠깐 살펴보자. A를 출발노드로 했을 때, 가장 왼쪽에 있는 G를 방문하고 G는 더 이상 연결된 정점이 없으므로 A로 돌아온다. 다음 방문하지 않은 정점인 C를 방문했을 때, D라는 방문하지 않은 정점이 있으므로 D를 방문한 후에 다시 A로 돌아오게 된다. 아래 문제를 통해서 DFS는 어떻게 구현하는지 알아보고 BFS를 복습해본다.

1260번: DFS와 BFS

public class Main {
	static StringBuilder sb = new StringBuilder();
	
	static class Graph {
        // 전체 정점 개수
		private int V;
        // 연결리스트를 통한 간선 표현
		private LinkedList<Integer> adj[];
		
		Graph(int v){
			V = v;
			adj = new LinkedList[v+1];
			for(int i = 1; i <= v; i++)
				adj[i] = new LinkedList();
		}
		
        // 양방향 간선으로 연결
		void addEdge(int v, int w) {
			adj[v].add(w);
			adj[w].add(v);
		}
		
		void sortList() {
			for(int i = 1; i<=V; i++) {
				Collections.sort(adj[i]);
			}
		}
		
        // 재귀를 통한 dfs 구현
		void dfs(int v, boolean visited[]) {
			sb.append(v + " ");
			visited[v] = true;
			Iterator<Integer> i = adj[v].listIterator();
			while(i.hasNext()) {
				int n = i.next();
				if(!visited[n])
					dfs(n, visited);
			}
		}
		
		void dfsInit(int v) {
			boolean visited[] = new boolean[V + 1];
			dfs(v, visited);
		}
		
		void bfs(int v) {
			boolean visited[] = new boolean[V + 1];
			LinkedList<Integer> queue = new LinkedList<Integer>();
			visited[v] = true;
			queue.add(v);
			while(!queue.isEmpty()) {
				v = queue.poll();
				sb.append(v + " ");
				Iterator<Integer> i = adj[v].listIterator();
				while(i.hasNext()) {
					int n = i.next();
					if(!visited[n]) {
						visited[n] = true;
						queue.add(n);
					}
				}
			}
		}
	}
	
	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());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int V = Integer.parseInt(st.nextToken());
		Graph g = new Graph(N);
		for(int i = 0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			g.addEdge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		g.sortList();
		g.dfsInit(V);
		sb.append("\n");
		g.bfs(V);
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

}

 

DFS는 일반적으로 재귀함수를 통해 구현하는데, 이는 인접한 방문하지 않는 노드들을 먼저 방문하기 위함이다. 위처럼 인접 리스트를 이용해 구현하는 경우 O(|V| + |E|) 만큼의 시간복잡도가 걸리며, 인접 행렬을 사용하는 경우 O(|V|^2) 만큼의 시간복잡도가 발생한다.

 

DFS의 경우 BFS와 달리 활용할 수 있는 추가적인 알고리즘들이 많이 있는데, 사이클 여부를 판단하거나 위상정렬을 구현하는데 주로 사용이 된다. 따라서 기본 매커니즘인 재귀를 통해서 어떻게 DFS를 구현하고 방문 순서를 어떻게 정의해줄 것인가를 익혀야 활용을 할 수 있게 된다.

---

2. 참고문제

1. [Silver 3] 바이러스

2606번: 바이러스

2. [Silver 2] 섬의 개수

4963번: 섬의 개수

3. [Gold 5] 트리와 쿼리

15681번: 트리와 쿼리