[이것이 취업을 위한 코딩 테스트다 with 파이썬] 3. DFS & BFS

그래프 탐색 알고리즘: DFS/BFS

• 탐색(Search): 많은 양의 데이터 중 원하는 데이터 찾는 과정
• 대표적인 그래프 탐색 알고리즘: DFS/BFS
• 코딩 테스트에서 매우 자주 등장하는 유형

---

스택 자료구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
• 입구와 출구가 동일한 형태로 스택을 시각화 가능

삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

Python

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력 [1, 3, 2, 5]
print(stack) # 최하단 원소부터 출력 [5, 2, 3, 1]

C++

#include <bits/stdc++.h>
using namespace std;

stack<int> s;

int main(void) {
	s.push(5);
    s.push(2);
    s.push(3);
    s.push(7);
    s.pop();
    s.push(1);
    s.push(4);
    s.pop();
    
    // 스택의 최상단 원소부터 출력
    while (!s.empty()) {
    	cout << s.top() << ' ';
        s.pop();
    }
}

// 1 3 2 5

Java

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Stack<Integer> s = new Stack<>();
        
        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop()
        s.push(1);
        s.push(4);
        s.pop();
        
        // 스택의 최상단 원소부터 출력
        while (!s.empty()) {
        	System.out.println(s.peek() + " "); 
            s.pop();
        }
    }
}

// 1 3 2 5

---

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능

 

삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()

Python

from collections import deque

# 큐(Queue) 구현 -> deque 라이브러리 사용
queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력 deque([3, 7, 1, 4])
queue.reverse() # 역순으로 바꾸기 
print(queue) # 나중에 들어온 원소부터 출력 deque([4, 1, 7, 3])

C++

#include <bits/stdc++.h>
using namespace std;

queue<int> q;

int main(void) {
	q.push(5);
    q.push(2);
    q.push(3);
    q.push(7);
    q.pop();
    q.push(1);
    q.push(5=4);
    q.pop();
    
    // 먼저 들어온 원소부터 추출
    while (!q.empty()) {
    	cout << q.front() << ' ';
        q.pop();
    }
}

// 3 7 1 4

Java

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Queue<Integer> q = new LinkedList<>();
        
        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll();
        q.offer(1);
        q.offer(4);
        q.poll();
        
        // 먼저 들어온 원소부터 추출
        while (!q.isEmpty()) {
        	System.out.print(q.poll() + " ");
        }
    }
}

// 3 7 1 4

---

재귀 함수(Recursive Function)

• 자기 자신을 다시 호출하는 함수
• 단순한 형태의 재귀 함수 예제
  • '재귀 함수를 호출합니다.' 라는 문자열 무한히 출력
  • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지 출력

def recursive_function():
	print("재귀 함수를 호출합니다.")
    recursive_function()

recursive_function()

재귀 함수의 종료 조건

• 문제 풀이에서 사용할 때는 종료 조건 반드시 명시
• 종료 조건 제대로 명시 X -> 함수 무한히 호출 될 수 있음
  • 종료 조건 포함한 재귀 함수 예제

def recursive_function(i):
	# 종료 조건 명시: 100번째 호출 -> 종료 
    if i == 100:
    	return
    print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
    recursive_function(i + 1)
    print(i, '번째 재귀함수를 종료합니다.')
    
recursive_function(1)

팩토리얼 구현 예제

• n! = 1 * 2 * 3 * ... * (n - 1) * n
• 수학적으로 0! = 1! = 1

# 반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
    # 1부터 n까지의 수 차례대로 곱하기
    for i in range(1, n + 1):
    	result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
	if n <= 1: # n이 1이하인 경우 -> 1 반환
    	return 1
    # n! = n * (n - 1)!
    return n * factorial_recursive(n - 1)

# 각각 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현: ', factorial_iterative(5)) // 120
print('재귀적으로 구현: ', factorial_recursive(5)) // 120

---

최대공약수 계산 (유클리드 호제법) 예제

유클리드 호제법

• 두 개의 자연수에 대한 최대공약수 구하는 대표적인 알고리즘
• 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R
• 이때 A와 B의 최대공약수 == B와 R의 최대공약수
• 재귀 함수로 작성
  • ex. GCD(192, 162)

def gcd(a, b):
	if a % b == 0:
    	return b
    else:
    	return gcd(b, a % b)

print(gcd(192, 162)) // 6

유의사항

• 재귀 함수 잘 활용하면 복잡한 알고리즘 간결하게 작성 가능
  • 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용
• 모든 재귀 함수 -> 반복문 이용하여 동일한 기능 구현할 수 있음
• 재귀 함수가 반복문보다 유리한 경우 / 불리한 경우 있음
• 컴퓨터가 함수 연속적으로 호출 -> 컴퓨터 메모리 내부의 스택 프레임에 쌓임
  • => 스택 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수 이용하는 경우 ↑

---

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

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(or 재귀 함수) 이용
• 탐색 시작 노드 -> 스택에 삽입, 방문 처리
  1. 스택의 최상단 노드에 방문 X 인접한 노드 하나라도 O -> 그 노드 스택에 넣고 방문 처리
  2. 방문 X 인접 노드 X -> 스택에서 최상단 노드 꺼냄
  3. 더 이상 2번의 과정 수행할 수 없을 때까지 반복

Python

# DFS 메서드 정의
def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드 -> 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
dfs(graph, 1, visited)

# 1 2 7 6 8 3 4 5

C++

# include <bits/stdc++.h>
using namespace std;

bool visited[9];
vector<int> graph[9];

void dfs(int x) {
	visited[x] = true;
    cout << x << ' ';
    
    for (int i = 0; i < graph[x].size(); i++) {
    	int y = graph[x][i];
        if (!visited[y]) dfs(y);
    }
}

int main(void) {
	/*
    	그래프 연결된 내용 생략
    */
    // dfs(1)
    return 0;
}

Java

import java.util.*;

public class Main {
	public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    
    // DFS 함수 정의
    public static void dfs(int x) {
    	// 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
        	int y = graph.get(x).get(i);
            
            if (!visited[y]) dfs(y);
		}
    }
    
    public static void main(String[] args) {
    	/*
        	그래프 연결된 내용 생략
        */
        // dfs(1)
    }
}

---

BFS(Breadth-First Search, 너비 우선 탐색)

• 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료 구조 이용
  1. 탐색 시작 노드 -> 큐에 삽입, 방문 처리
  2. 큐에서 노드 꺼냄, 해당 노드의 인접 노드 중 방문 X 노드를 모든 큐에 삽입하고 방문 처리
  3. 더 이상 2번의 과정 수행할 수 없을 때까지 반복

Python

from collection import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현 -> deque 라이브러리 사용
    qeueu = deque([start])
    # 현재 노드 방문 처리
    visited[start] = True
    
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        
        # 아직 방문 X 인접한 원소들 -> 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
        

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

# 1 2 3 8 7 4 5 6

C++

#include <bits/stdc++.h>
using namespace std;

bool visited[9];
vector<int> graph[9];

void bfs(int start) {
	queue<int> q;
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
    	int x = q.front();
        q.pop();
        cout << x << ' ';
        
        for (int i = 0; i < graph[x].size(); i++) {
        	int y = graph[x][i];
            
            if (!visited[y]) {
            	q.push(y);
                visited[y] = true;
            }
        }
    }
}

int main(void) {
	// 그래프 연결된 내용 생략
    // bfs(1)
    return 0;
}

Java

import java.util.*;

public class Main {
	public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    
    // BFS 함수 정의
    public static void bfs(int start) {
    	Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드 방문 처리
        visited[start] = true;
        
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
        	// 큐에서 하나의 원소 뽑아 출력
            int x = q.poll();
            System.outprint(x + " ");
            
            // 해당 원소와 연결된, 아직 방문 X 원소들 -> 큐에 삽입
            for (int i = 0; i < graph.get(x).size(); i++) {
            	int y = graph.get(x).get(i);
                
                if (!visited[y]) {
                	q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }
    
    // 메인 함수 생략
}

---