[211216] 코딩 테스트를 위한 깊이 우선 탐색, 너비 우선 탐색 ( DFS & BFS )

모든 게시물은 macOS Monterey 12.0.1 버전 기준으로 작성하였습니다.
'이것이 취업을 위한 코딩 테스트다 with 파이썬' 토대로 작성하였습니다.

 

< 복습 >

 

• for문 쓸 때 무조건 for i in range() 가지 말고 리스트 그대로 iteration 할까도 고려하자.
• if l[i] == 0 or 1 으로 조건문 걸면 False or True로 인식해서 다 참으로 간다.(그런듯?)
• ㅣ = [] 형태로 리스트 초기화 후 for문에 l[i] 인덱싱하면 out of index 나온다.
• 리스트 sorting 할 때 l = l.sort() 하면 값 없어진다. 그냥 l.sort() 써라.
• 리스트 크기를 size(l)로 구할 수 없다. len(l)로 구해라.
• 그래프 모델링 할 때는 노드 인덱싱과 맞추기 위해 그래프의 첫 리스트를 []로 초기화한다.
• DFS는 재귀 함수 형태로 해결하고, BFS는 while queue로 반복문을 건다.
• BFS는 방문 처리하기 전에 popleft로 원소를 빼주고, 방문처리하면 append 잊지 말자.

 

---

 

그래프 탐색 알고리즘

 

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.

대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다.

코딩 테스트에서 자주 등장하는 유형으로 이를 이해하기 위해서는

두 가지 기본 자료구조인 스택과 큐에 대한 이해가 필요하다.

여기서 자료구조란 데이터를 표현, 처리하기 위한 구조로 삽입과 삭제로 운영한다.

실제로 스택과 큐를 이용할 때는 오버플로와 언더플로에 대한 고민을 해야 하는데

오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 양이

가득 찬 상태에서 삽입 연산을 수행할 때 발생한다.

반대로 자료구조에 어떤 데이터도 들어 있지 않은 상태에서

삭제 연산을 수행하면 언더플로가 발생한다.

 

[ 스택, Stack ]

스택은 박스 쌓기에 비유할 수 있다.

먼저 들어 온 데이터가 나중에 나가는 선입후출의 자료구조다.

 

 

파이썬에서 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다.

단순리 리스트 자료형을 이용하여 가장 오른쪽 원소를 삽입하는 append와

가장 오른쪽 원소를 꺼내는 pop을 method를 통해 stack을 구현한다.

append와 pop의 시간복잡도는 O(N)이기에 stack으로 활용하기에 적합하다.

stack을 print(stack[::-1])을 통해 출력하면 먼저 나가는 원소가 왼쪽으로 온다.

[ 큐, Queue ]

큐는 대기 줄에 비유할 수 있다.

놀이공원에 줄을 서면 먼저 들어온 사람이 먼저 들어가게 되는 ( 선입선출 )

나중에 온 사람이 나중에 들어가기 때문에 흔히 '공정한' 자료구조라고 비유된다.

 

 

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque를 활용한다.

deque는 데이터를 넣고 빼는 것이 리스트나 queue 라이브러리보다 효율적이다.

대부분 코딩 테스트에서 collections 과 같은 기본 라이브러리 사용을 허용한다.

코드로 구현한 것을 보면 알겠지만 앞서 설명을 위해 터널로 표현한 것과 순서가

반대로 나타남에 주의하자. queue.reverse()로 출력하면 터널 그림과 일치한다.

 

queue를 구현할 때는 리스트가 아닌 deque를 이용하는 것이 시간복잡도가 좋다.

리스트를 이용해서 특정 인덱스에 존재하는 원소를 꺼내기 위해 pop을 쓰면

원소를 꺼낸 뒤에 원소의 위치를 조정하는 과정이 필요하기 때문에

꺼내는 연산 자체가 O(N)의 시간복잡도를 요하게 된다.

[ 재귀 함수, Recursive Function ]

 

 

DFS와 BFS를 구현하려면 재귀 함수를 이해하고 있어야 한다.

위 코드를 실행하면 '재귀 함수를 호출합니다.' 라는 문장을 무한히 출력한다.

 

 

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 명시해야 한다.

그렇다면 이러한 재귀 함수를 이용하는 예시에는 어떤 것이 있을까?

 

대표적 예제로는 팩토리얼 문제가 있다.

팩토리얼을 반복적으로 구현한 방식과 재귀적으로 구현한 두 방식을 비교해보자.

 

 

반복문 대신에 재귀 함수를 이용하면 그 코드가 더 간결해진다.

이는 재귀 함수가 수학의 점화식을 그대로 소스코드로 옮겼기 때문이다.

점화식은 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다.

그리고 이는 추후 '다이나믹 프로그래밍'을 배울 때 중요하게 사용된다.

 

---

 

DFS ( Depth - First Search )

 

 

오른쪽 코드에 대한 설명은 필요할 것 같다.

우선 graph를 정의하는 방식에는 인접 행렬(Adjacency Matrix)과

인접 리스트 (Adjacency List)가 있다. 여기서는 리스트를 활용했으니 후자겠다.

 

궁금증 하나. graph의 index 0은 왜 빈 리스트인가? 

왼쪽 그림에서 각 노드들은 자연수로 이루어져 있기에 그 인덱싱을 따라가기 위해.

 

궁금증 둘. visited = [False] * 9는 무엇인가?

노드는 0개인데 역시 0번째 인덱스 사용하지 않으려고 한 것이고,

방문 처리를 위한 boolean list다.

 

궁금증 셋. 왼쪽 코드를 설명해달라.

dfs 함수는 그래프 정보와 노드 인덱스 그리고 방문 정보를 받는다.

해당 노드를 방문 처리한 뒤 그 노드를 프린트하고,

해당 노드에 연결된 다른 노드를 차례대로 탐색하며 방문처리가 되어있지 않으면

그 노드를 대상으로 같은 함수를 실행한다.

 

깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 쉽다.

또, 스택을 이용하기에 실제 구현은 재귀 함수를 이용했을 때 매우 간단해진다.

 

---

 

BFS ( Breadth - First Search )

 

 

DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다면

BFS는 그 반대다. BFS 구현에는 선입선출 방식인 큐 자료구조를 활용한다.

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게

먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

BFS 역시 다양한 대기업 코딩 테스트에서 빈번하게 출제되고 있으며,

특히 최단경로 문제를 해결하기 위한 목적으로도 효과적으로 활용된다.

DFS에 비해 개인적으로 그 원리 이해가 어려워 모든 과정을 기록하려 한다.

 

 

위 결과를 분석해보자. 2와 3 그리고 8은 1로부터 거리가 1인 노드들이다.

7과 4 그리고 5는 1로부터 거리가 2, 그리고 6은 1로부터 거리가 3인 노드다.

이처럼 각 간선의 비용이 동일한 상황에서 최단거리 문제 해결을 위해 사용된다.

 

너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다는 점에서 구현이 쉽다.

실제 구현함에 있어 앞서 언급한 대로 deque 라이브러리를 활용하는 것이 좋으며

탐색을 수행함에 있어 O(N)의 시간 복잡도가 소요된다. 

 

 

오른쪽 코드는 DFS를 진행할 때와 똑같으니 설명을 생략하고 왼쪽을 보자.

역시 bfs 함수는 graph와 시작 node 그리고 visited 리스트를 인풋으로 받는다.

deque를 통해 queue 자료구조를 하나 만든다. 여기서 DFS와의 가장 큰 차이는

stack 구조를 활용하지 않았으니 재귀 함수를 이용하지는 않는다는 것이다.

대신에 queue가 빌 때까지 queue에 먼저 들어간 원소를 제거하고,

그 node에 연결된 다른 node를 append 한 후 방문처리 한다.

 

---

 

DFS & BFS 코딩 테스트 연습 문제

 

1. 음료수 얼려 먹기

 

 

난이도가 1.5라고 써있는데 이를 보고 DFS를 떠올리는 것조차 나에게는 버겁다.

그래프로 모델링하고 특정 지점에서 연결된 모든 노드를 방문하면서 방문처리.

이후에 1로 처리된 장벽은 이동할 수 없도록 한다는 것이 전략이다.

 

 

자, 코드를 이해하여 보자..

먼저 그래프에 2차원 리스트로 맵 정보를 입력 받는다.

각 위치에서 DFS를 수행하고, 해당 위치에서 True라면 카운트를 하나 늘린다.

 

DFS 함수를 보자. 특정 지점을 방문처리를 하고 상하좌우에 방문처리를 하는데

만약 그 지점이 이미 방문한 지점이라면 바로 False를 출력하니 카운트는 그대로다.

상하좌우에 재귀적 처리를 할 때도 만약 범위를 벗어나면 False를 출력하고,

그 노드들에도 방문처리를 해가면서 카운트를 늘려갈 수 있다.

 

y &gt;= m 인데 오타다..

---

 

DFS & BFS 코딩 테스트 연습 문제

 

2. 미로 탈출

 

 

진지하게 이런 문제들이 테스트에 나왔을 때 그 자리에서 풀 수 있을 지는 미지수다.

(1,1) 위치에서 BFS를 통해 모든 노드에 대한 최단거리를 구하여 문제를 해결한다.

 

 

어렵다,,,,,,