나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리해보자. (내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저'임을 사전에 밝힙니다.)
이전 내용이었던 그리디 알고리즘 & 구현이 궁금하다면 아래 링크를 참조하고,
https://jjuke-brain.tistory.com/46
Ch01. 그리디 알고리즘 & 구현 (feat. 이것이 취업을 위한 코딩 테스트다)
나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다' 강의와 교재 내용을 공부하고 그 내용을 정리해보자. (내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다
jjuke-brain.tistory.com
영상은 다음과 같이 업로드한다!
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
목차
1. 탐색이란?
DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.
여기서 탐색(Search)이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
실제로 다양한 알고리즘에서 특정 조건에 맞는 데이터가 존재하는지, 만약 존재한다면 어떤 위치에 존재하는지 등을 찾고자 하는 목적으로 탐색 알고리즘을 사용한다.
대표적인 그래프 탐색 알고리즘으로 DFS와 BFS가 있는데, 이 둘은 코딩 테스트에서 매우 자주 등장하는 유형으로, 반드시 숙지해 두도록 하자.
특히 국내 대기업 공채에서는 DFS, BFS를 적절히 활용해야 하는 문제가 자주 출제되고 있다.
본격적으로 DFS, BFS에 대해 알아보기 이전에, 반드시 알아두고 넘어가야 할 두 가지 자료 구조에 대해 먼저 알아보자.
2. 스택(Stack) 자료 구조
스택 자료 구조는 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
스택은 위와 같은 '박스 쌓기'로 이해하면 쉽다. 박스를 쌓는 과정은 입구와 출구가 동일한 형태로 시각화된다.
여러 개의 박스를 쌓아야 할 때, 아래 쪽에서부터 박스를 차례대로 올려 둔다. 그렇게 쌓아올린 박스를 빼내고자 할 때에는 위쪽의 박스부터 꺼내게 된다.
이러한 스택 구조는 DFS 알고리즘 뿐만 아니라 매우 다양한 알고리즘에서 사용되기 때문에 스택 자료구조의 동작 방법과 사용방법에 대해 알아둘 필요가 있다.
1) 스택 동작 예시
스택 자료구조는 삽입과 삭제라는 두 가지 연산으로 구성된다.
예를 들어 스택 자료구조에 다음과 같이 여러 데이터를 삽입 또는 삭제하는 예시를 살펴보자.
- 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
위 예시와 같이, 스택 자료구조에서는 입구와 출구가 똑같으므로, 들어올 때에도 나갈 때에도 오른쪽에 쌓이거나 삭제된다.
(1) Python 스택 구현 예제
파이썬에서 스택을 구현하려면, 추가적인 라이브러리를 이용할 필요 없이 단순히 리스트 자료형을 사용하면 된다.
- append() → 삽입 연산
- pop() → 삭제 연산
stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
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]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력
실행 결과는 다음과 같다.
- [1, 3, 2, 5]
- [5, 2, 3, 1]
이때 append()메소드와 pop()메소드의 시간 복잡도는 상수 복잡도를 갖기 때문에, 스택 자료구조를 활용하기에 적절하다.
(2) C++ 스택 구현 예제
C++에서는 stl 라이브러리에서 스택 자료구조를 지원한다.
- push() → 삽입
- pop() → 삭제
#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
stack<int> s; 에서 볼 수 있듯이, stack 자료구조에 int 자료형을 이용하겠다고 명시해주어야 한다.
3. 큐(Queue) 자료구조
이어서 큐 자료구조에 대해 알아보자. 큐 자료구조는 먼저 들어온 데이터가 먼저 나가는 (선입선출) 자료구조이다.
이것을 쉽게 이해하자면, 입구와 출구가 모두 뚫려있는 터널과 같은 모습을 떠올려보면 쉽다.
예를 들어, 은행 창구 등에서 사람들이 번호표를 뽑고 대기하고 있는 모습 등을 떠올려 볼 수 있다.
흔히 우리가 차례대로 어떠한 작업을 실행한다고 하면 '대기열'이라는 표현을 자주 사용하는데, 실제로 영어권에서는 이 큐(Queue)라고하는 것은 일반적으로 차례대로, 먼저 들어온 데이터가 먼저 처리를 받는 일종의 대기열을 나타내고자 할 때 큐라고 표현한다.
1) 큐 동작 예시
아래 그림과 같이 데이터가 왼쪽에서 들어갔다가 오른쪽으로 나가는 형태를 생각해보자. (실제 구현 상에서는 조금 다를 수 있지만 방향보다는 삽입과 삭제에 대한 개념을 잡는다고 생각하자.)
- 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
각 삽입 시, 삭제 시 어떤 원소가 어디에 삽입 되고 삭제 되는지 잘 살펴보자.
(1) Python 큐 구현 예제
큐 자료구조는 파이썬에서 'deque' 라이브러리를 사용할 수 있다.
엄밀히 말하면 단순히 리스트 자료형을 이용하여 큐를 구현할 수 있지만, 리스트 자료형을 이용하는 경오 기능적으로는 큐를 구현할 수 있지만, 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있으므로 꼭 deque 라이브러리를 사용하도록 하자.
- append() → 삽입 (list에서와 동일하게 동작한다.)
- popleft() → 삭제 (위 예시와 달리 오른쪽에서 삽입되고, 왼쪽에서 삭제된다고 가정하자.)
from collections import deque
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
출력 결과는 다음과 같다.
- deque([3, 7, 1, 4])
- deque([4, 1, 7, 3])
리스트 자료형보다 deque을 사용하는 것이 효율적인 이유는, 파이썬에서 리스트를 통해 특정 인덱스의 원소를 꺼내기 위해 pop 메소드를 실행하게 되면, 원소를 꺼낸 뒤에 원소의 위치를 조정하는 과정이 필요하기 때문에 원소를 꺼내는 연산 자체가 O(k)만큼의 시간복잡도가 요구된다.
(2) C++ 큐 구현 예제
다음으로 C++에서 큐를 구현하기 위해서는 stl 라이브러리의 queue를 이용하면 된다.
- push() → 삽입
- pop() → 삭제
- front() → 가장 먼저 들어온 데이터 반환
#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(4);
q.pop();
// 먼저 들어온 원소부터 추출
while (!q.empty()) {
cout << q.front() << ' ';
q.pop();
}
}
출력 결과는 다음과 같다.
- 3 7 1 4
메소드, 선언 방법 등은 stack과 거의 비슷하다.
4. 재귀 함수
다음으로, 재귀함수에 대해 알아보자. 재귀 함수(Recursive Function)란, 자기 자신을 다시 호출하는 함수를 말한다. 이러한 재귀함수는 우리가 다루게 될 DFS를 실질적으로 구현할 때 자주 사용되는 방법 중 하나이므로, 꼭 이해하고 넘어가자.
Recursive라는 단어는 '재귀적인'이란 뜻을 갖는데, 프로그램을 작성할 때 '재귀적으로 작성한다, 'Recursive하게 동작하도록 한다'라는 말이 쓰인다면, 재귀함수가 사용된다는 의미이다.
1) 재귀 함수 예제
단순한 형태의 재귀 함수 예제를 살펴보자.
- '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다.
- 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()
위 예시는 단순히 메시지를 무한히 출력하는 예시이다. 메인 함수에서 recursive_function()을 수행하게 되면 반복적으로 자기 자신을 호출함으로써 내용을 무한히 출력한다.
단, 파이썬에서는 최대 재귀 깊이 제한이 있기 때문에 별다른 설정 없이도 위 코드를 실행하면 'maximum recursion depth exceeded'라는 오류메세지를 출력하게 되고, 프로그램이 종료된다.
실제로 컴퓨터 시스템 상에서 함수가 재귀적으로 호출이 되면, 스택과 같은 형태로 동작한다. 즉, 일종의 스택 자료구조 안에 함수에 대한 정보가 차례대로 담겨서 컴퓨터 메모리에 올라가게 된다. 메모리는 한정된 자원을 갖기 때문에 무작정 함수가 종료되지 않고 계속해서 쌓아 올려서 재귀적으로 호출만 하게 되면 메모리가 가득차는 문제가 발생할 수 있기 때문에 제한을 걸어 둘 수 있다.
만약 우리가 제한 없이 재귀 함수를 호출하고자 한다면, 이러한 재귀 자연을 느슨하게 만드는 방법을 이용하거나, 별도로 스택 자료구조를 사용하여 스택 개체를 따로 만들어서 그것을 이용하는 방법을 사용할 수 있다.
코딩테스트 수준에서는 이와 같이 일반적인 재귀 함수를 사용해도 통과할 수 있도록 출제되는 경우가 많다.
2) 재귀 함수의 종료 조건
재귀 함수를 이용하면, while이나 for문을 이용하지 않고도 어떤 내용을 반복적으로 수행할 수 있다. 다만 일반적인 경우 무한 루프를 이용할 것이 아니라면 일반적인 코딩테스트에서 이 재귀 함수를 문제풀이에 사용할 때에는 재귀 함수의 종료 조건을 반드시 명시하여야 한다.
즉, 언젠가는 프로그램이 정해진 값을 반환할 수 있도록 만들어야 한다.
실제로 종료 조건을 사용하여 재귀 함수가 특정 시점에 종료될 수 있도록 조건을 만든 결과가 다음과 같다.
- 재귀 함수를 문제 풀이에서 사용할 때에는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
- 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
- 종료 조건을 포함한 재귀함수 예제
def recursive_funciton(i):
# 100번째 호출할 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)
위와 같이 변수 i를 이용하여 종료 조건을 만들어 줄 수 있다.
위 코드의 결과는 스택의 삽입과 삭제 연산과 같이 일어난다.
'i 번째 재귀함수에서 i+1 번째 재귀함수를 호출합니다.'의 내용이 1부터 99까지 이어지고,
i가 100이 되었을 때 함수가 종료되는데, 나중에 호출되었던 함수부터 종료되면서
'i 번째 재귀함수를 종료합니다.'의 내용이 99부터 1까지 나오게 된다.
3) 팩토리얼 구현 예제
- 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))
print('재귀적으로 구현: ', factorial_recursive(n-1))
코드에서 factorial_iterative 함수는 반복문을 사용하여 팩토리얼을 구현하였고, factorial_recursive 함수는 점화식과 재귀함수를 통해 팩토리얼을 구현하였다.
재귀함수를 통해 구할 경우, 수학적인 점화식을 사용하여 구현하므로 코드가 더 간결하고 직관적일 수 있고, 반복문을 사용하지 않는다는 점에서 장점을 갖는다.
4) 유클리드 호제법 예제
재귀함수를 효과적으로 사용할 수 있는 또다른 예시로 '유클리드 호제법'을 들 수 있다. 이는 최대공약수를 계산하고자 할 때 사용할 수 있는 방법이다.
- 유클리드 호제법
- 두 자연수 A, B에 대해 (A > B) A를 B로 나눈 나머지를 R이라 하자.
- 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다. (이에 대한 증명은 수학적으로 알려져 있지만, 여기에서 설명하지는 않겠다.)
유클리드 호제법의 아이디어를 그대로 재귀함수로 작성하라.
예를 들어, GCD(192, 162)를 구해보자. 단, 여기서 GCD는 Great Common Divisor의 약자로, 최대공약수를 뜻한다.
192를 162로 나누면 나머지가 30이다. 따라서 192와 162의 최대공약수는 162와 30의 최대공약수와 같다.
이를 반복하면 162와 30의 최대공약수는 162를 30으로 나눌 때 나머지가 12이고, 30과 12의 최대공약수와 같아진다.
따라서 GCD(192, 162) = GCD(162, 192 % 162 = 30) = GCD(192 % 162 = 30, 162 % (192 % 162) = 12)이다.
이를 표로 나타내면 다음과 같다.
| 단계 | A | B |
| 1 | 192 | 162 |
| 2 | 162 | 30 |
| 3 | 30 | 12 |
| 4 | 12 | 6 |
위 과정을 직관적으로 코드로 옮겨보자.
def gcd(a, b):
if (a % b) == 0:
return b
else:
return gcd(b, a%b)
print(gcd(192, 162))
이렇게 수학적인 로직을 그대로 코드로 옮길 수 있다.
또한 이렇게 함수를 작성하면 함수의 동작 과정 상 처음 함수를 호출할 때 꼭 a가 b보다 크지 않아도 괜찮다. 단지 a와 b를 순서에 상관 없이 인자 값으로 넣어주게 되면 정상적으로 동작한다. 이렇게 함수가 직관적이고 짧아진다.
5) 재귀 함수 사용 시 유의사항
앞에서도 언급했듯이, 재귀 함수를 잘 활용한다면, 복잡한 알고리즘을 간결하게 작성할 수 있다.
단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 상황에 맞게 이용해야 한다.
그리고 이론적으로 모든 재귀함수는 반복문을 사용하여 동일하게 기능을 구현할 수 있다. 반대로 반복문을 이용해 구현한 코드도 재귀함수로 구현할 수 있다.
이때 재귀함수가 반복문보다 유리한 경우도, 반복문이 더 유리한 경우도 있기 때문에 문제를 풀기 위해 더 좋은 방법을 고려해 보아야 한다.
마지막으로 컴퓨터가 함수를 연속적으로 호출하면, 컴퓨터 메모리 내부의 스택 프레임에 쌓이게 된다. 이러한 특성 때문에 스택을 사용해야 할 때, 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
대표적인 예시로 DFS를 더욱 간결하고 짧은 코드로 작성하기 위해서 재귀 함수를 사용하기도 한다.
5. DFS (Depth-First Search)
DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
1) DFS의 동작 과정
DFS는 스택 자료구조 또는 재귀함수를 사용하며, 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 즉, 매번 최상단 원소를 기준으로 방문하지 않은 인접 노드가 있으면 그 노드로 방문을 수행하는 것이다.
- 더 이상 2번 과정을 할 수 없을 때까지 반복한다.
예시를 통해 알아보자.
위 사진과 같은 방향이 없는 그래프가 있다. 이때 실제 DFS는 인접한 노드가 여러 개일 수 있기 때문에 어떤 노드부터 방문할지를 결정하기 위한 기준이 필요하다. 이는 문제에 주어지며, 어떤 노드부터 방문하는지 상관 없는 경우도 있다.
예시에서는 번호가 낮은 인접 노드부터 방문하고, 시작 노드는 1로 두자.
[Step 1] 시작 노드인 '1'을 스택에 삽입하고, 방문 처리를 한다.
[Step 2] 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '2', '3', '8'이 있다. 이 중에서 가장 작은 노드인 '2'를 스택에 넣고 방문 처리를 한다.
[Step 3, 4] '2'에서 출발하여 같은 과정을 반복한다.
[Step 5] 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드가 없으므로, 스택에서 '6' 노드를 꺼낸다.
[Step 6] 최상단 노드를 다시 '7'로 두고, 방문하지 않은 인접 노드인 '8'이 있다. 따라서 '8' 노드를 스택에 넣고 방문 처리를 한다.
이러한 과정을 반복하면 전체 노드의 탐색 순서, 즉 스택에 들어간 순서는 다음과 같다.
실제로 위와 같이 최대한 깊게 들어가는 형태로 동작을 하기 때문에, 스택 자료구조 대신에 재귀 함수를 이용하여 구현할 수 있다.
2) DFS 소스코드 예제 (Python)
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
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)실행 결과는 다음과 같다.
- 1 2 7 6 8 3 4 5
그래프를 표현하기 위해 2차원 리스트를 사용하였다. 문제에서 노드의 번호가 1번부터 시작하는 경우가 많기 때문에, 0번 index는 비워두고, 1번부터 연결된 노드들을 표현해준다. 이 방식을 '인접 리스트 방식으로 표현한다'고 말한다.
또한 방문된 정보 리스트에서도 0번 index를 사용하지 않기 위해 1~8번 노드보다 더 많은 9개의 원소를 갖는 visited 리스트를 형성한다.
3) DFS 소스코드 예제 (C++)
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;
}
6. BFS (Breadth-First Search)
BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
BFS 알고리즘 또한 다양한 대기업 코딩테스트 문제에서 출제가 되고 있으며, 특히 BFS 알고리즘은 특정 조건에서 최단 경로 문제를 해결하기 위한 목적으로도 효과적으로 사용될 수 있다.
또한 큐 자료구조가 사용되기 때문에, 각 프로그래밍 언어마다 큐 자료구조를 어떻게 사용할 수 있는지에 대한 내용도 숙지해 두어야 한다.
1) BFS 동작 과정
BFS는 큐 자료구조를 사용하며, 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 큐에 삽입하고, 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. DFS를 수행할 때에는 인접하지 않은 노드에 대해 다시 한번 스택에 넣으면서 수행하였지만, BFS는 해당 시점에서 인접한 노드를 한 번에 전부 큐에 넣는다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
마찬가지로 예시를 통해 이해해보자.
DFS에서와 마찬가지로, 무방향 그래프가 있다. 방문 기준은 번호가 낮은 인접 노드부터이고, 시작 노드는 1이다.
[Step 1] 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다.
단, 아래 사진에서 큐는 위에서 들어와서 아래로 나간다고 가정한다.
[Step 2] 큐에서 노드 '1'을 꺼내 방문하지 않은 노드인 '2', '3', '8'을 큐에 모두 삽입하고 방문 처리를 한다.
[Step 3, 4] 기준 노드에 대해 방문하지 않은 인접 노드들을 큐에 삽입하고 방문 처리를 하는 과정을 반복한다.
[Step 5] 큐에서 노드'8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.
전체 결과는 아래와 같다.
BFS의 탐색 순서를 살펴보면, 시작 노드로부터 가까운 노드를 우선적으로 탐색하므로, '넓게' 노드를 방문 처리하게 된다. 노드 2, 3, 8은 1로부터 거리가 1, 노드 4, 5, 7은 거리가 2 등의 특징을 갖는다.
이러한 특징 대문에 각 간선의 비용이 모두 동일한 상황에서의 최단거리 문제를 해결하기 위해 BFS를 사용할 수 있다.
2) BFS 소스코드 예제 (Python)
이제 파이썬을 이용하여 BFS를 구현하는 코드를 살펴보자.
from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력하기
v = queue.popleft()
print(v, end=' ')
# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
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
DFS에서와 마찬가지로 그래프와 방문된 정보를 표현해준다.
3) BFS 소스코드 예제 (C++)
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;
}
로직은 파이썬과 똑같다!
7. DFS, BFS 예제 - 음료수 얼려 먹기
코딩테스트에 출제되는 DFS, BFS 문제의 특징은, 처음에는 구현이 어렵고 복잡한데, 어느 정도 익히고 나면 쉬워진다. 따라서 예제를 잘 풀어보고, 빠르게 체화시키는 것이 중요하다.
Q) N × M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
예를 들어 다음 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.
- 입력 조건
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 ≤ N, M ≤ 1,000)
- 두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
- 출력 조건
- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
- 입력 예시
- 4 5
- 00110
- 00011
- 11111
- 00000
- 출력 예시
- 3
1) 문제 해결 아이디어
이 문제는 '연결 요소 찾기', 즉 Connected Component를 찾는 문제로 볼 수 있다.
문제는 DFS 혹은 BFS로 해결할 수 있다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로, 그래프 형태로 모델링할 수 있다. 다음과 같이 3 × 3 크기의 얼음 틀이 있다고 가정하고 생각해보자.
위와 같이 그래프 형태로 모델링 할 수 있다. 같은 색의 block들은 인접한 노드인 것이다.
이때 특정 지점에서 DFS 혹은 BFS를 수행하여 이동 가능한 모든 경우에 대해 방문 처리를 진행하도록 할 수 있다.
예를 들어, 가장 왼쪽 위에 있는 노드(0,0 노드라 지칭한다.)에 대해 시작을 하여 연결된 노드를 모두 방문하면서 방문 처리를 하게 되면, (1,0)노드와 (0,1) 노드 총 3개의 노드가 방문 처리가 된다. 이후의 인접부들의 노드들은 값이 1이기 때문에 이동이 불가능한 노드로 처리하면 될 것이다. 이런 과정을 거치면 하늘색 block만 방문 처리가 이루어지는 결과를 얻게 된다.
이 과정을 모든 노드에 대해 수행하여 방문 처리가 이루어지는 지점에서만 카운트를 수행하면 전체 block이 몇개인지 알 수 있게 된다.
2) DFS로 문제를 해결하는 방법
DFS를 활용하는 알고리즘은 다음과 같다.
- 특정 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서(연결된 노드 중) 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보며 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문하게 된다.
- 모든 노드에 대해 1, 2번 과정을 반복하면서 방문하지 않은 지점의 수를 카운트한다.
(1) Python 코드
Python 코드는 다음과 같다.
import sys
fin = sys.stdin.readline
# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
# 주어진 범위를 벗어나는 경우 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 현재 노드를 아직 방문하지 않았다면
if graph[x][y] == 0:
# 해당 노드 방문 처리
graph[x][y] = 1
# 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x - 1, y)
dfs(x, y - 1)
dfs(x + 1, y)
dfs(x, y + 1)
return True
return False
# N, M을 공백을 기준으로 구분하여 입력 받음
n, m = map(int, fin().rstrip().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
# 현재 위치에서 DFS 수행
if dfs(i, j) == True:
result += 1
print(result) # 정답 출력
결과적으로 DFS가 한번 쓰이게 되면, 해당 노드와 연결된 모든 노드들이 방문 처리가 되기 때문에 처음 방문할 때에만 result가 증가한다.
(2) C++ 코드
C++ 코드는 다음과 같다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int graph[1000][1000];
// DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
bool dfs(int x, int y) {
// 주어진 범위를 벗어나는 경우에는 즉시 종료
if (x <= -1 || x >=n || y <= -1 || y >= m) {
return false;
}
// 현재 노드를 아직 방문하지 않았다면
if (graph[x][y] == 0) {
// 해당 노드 방문 처리
graph[x][y] = 1;
// 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
dfs(x - 1, y);
dfs(x, y - 1);
dfs(x + 1, y);
dfs(x, y + 1);
return true;
}
return false;
}
int main() {
// N, M을 공백을 기준으로 구분하여 입력 받기
cin >> n >> m;
// 2차원 리스트의 맵 정보 입력 받기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &graph[i][j]);
}
}
// 모든 노드(위치)에 대하여 음료수 채우기
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 현재 위치에서 DFS 수행
if (dfs(i, j)) {
result += 1;
}
}
}
cout << result << '\n'; // 정답 출력
}
입력을 받을 때 공백 없이 0과 1의 조합으로 입력이 중지므로, scanf를 통해 한 문자씩 입력을 받는다.
DFS 수행 로직은 파이썬과 같다.
8. DFS, BFS 예제 - 미로 탈출
다음으로 미로 탈출 문제를 살펴보자.
Q) 당신은 N × M 크기의 직사각형 형태의 미로에 갇혔다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 당신의 위치는 (1, 1)이며 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다.
이때 당신이 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 단, 칸을 셀 때에는 시작 칸과 마지막 칸을 모두 포함하여 계산한다.
- 입력 조건 : 첫째 줄에 두 정수 N, M (4 ≤ N, M ≤ 200)이 주어진다. 다음 N개 줄에는 각각 M개의 정수 (0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
- 출력 조건 : 첫째 줄에 최소 이동 칸의 개수를 출력한다.
- 입력 예시
- 5 6
- 101010
- 111111
- 000001
- 111111
- 111111
- 출력 예시
- 10
1) 문제 해결 아이디어
BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에 간선의 비용이 모두 같을 때 최단거리를 탐색하는 데에 사용된다.
상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일하므로, (1, 1)지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.
예를 들어, 다음과 같이 3 × 3 크기의 미로가 있을 때, 이는 오른쪽의 그래프로 모델링할 수 있다.
2) BFS로 문제를 해결하는 방법
모델링한 이후 어떤 과정을 거쳐 문제를 해결할 수 있는지 살펴보자.
[Step 1] 처음에 (1, 1)의 위치에서 시작한다. 해당 노드를 큐에 담는다.
[Step 2] (1, 1) 좌표에서 상, 하, 좌, 우로 탐색을 진행할 경우, 바로 옆 노드인 (1, 2) 위치의 노드를 방문하게 되고, 새롭게 방문하는 (1, 2) 노드의 값을 2로 바꾸게 된다.
시작 위치와 마지막 위치를 포함해서 마지막 위치까지 도달하는 최단 경우에 포함되어 있는 노드의 수를 출력하는 것이므로, (1, 2) 노드까지는 거리가 2라고 할 수 있다.
이어서 (1, 2)노드 또한 큐에 담기게 되고, 다시 이 노드를 꺼낸 후에 마찬가지로 상하좌우에 연결되어 있는 노드를 확인하여 인접한 노드인 (2, 2)노드까지 방문을 수행한다. 해당 노드를 큐에 넣을 때, 방문 처리를 수행한 뒤에 그 이전 지점까지의 최단 거리에 1을 더한 값을 기록하여 최단 거리를 갱신한다.
이 과정을 반복하면 다음과 같은 결과가 나온다.
(1) Python 코드
미로 탈출 파이썬 답안 예시는 다음과 같다.
from collections import deque
import sys
fin = sys.stdin.readline
# BFS 소스코드 구현
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복
while queue:
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue:
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue:
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1 # 최단 거리 갱신
queue.append((nx, ny))
return graph[n - 1][m - 1]
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, fin().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, fin())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# BFS를 수행한 결과 출력
print(bfs(0, 0))
BFS 로직을 잘 이해하였다면 코드를 이해하는 데 무리가 없을 것이다.
(2) C++ 코드
다음으로 C++ 코드를 살펴보자.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int graph[201][201];
// 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int bfs(int x, int y) {
// 큐(Queue) 구현을 위해 queue 라이브러리 사용
queue<pair<int, int> > q;
q.push({x, y});
// 큐가 빌 때까지 반복하기
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
// 현재 위치에서 4가지 방향으로의 위치 확인
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 미로 찾기 공간을 벗어난 경우 무시
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
// 벽인 경우 무시
if (graph[nx][ny] == 0) continue;
// 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if (graph[nx][ny] == 1) {
graph[nx][ny] = graph[x][y] + 1;
q.push({nx, ny});
}
}
}
// 가장 오른쪽 아래까지의 최단 거리 반환
return graph[n - 1][m - 1];
}
int main(void) {
// N, M을 공백을 기준으로 구분하여 입력 받기
cin >> n >> m;
// 2차원 리스트의 맵 정보 입력 받기
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%1d", &graph[i][j]);
}
}
// BFS를 수행한 결과 출력
cout << bfs(0, 0) << '\n';
return 0;
}
이상으로 DFS, BFS 알고리즘 강의 내용 정리를 마친다.
최근댓글