이것이 코딩테스트다 챕터 5 DFS/BFS

DFS/BFS를 알기 전 기본 지식

1. 스택(stack)

선입후출(FILO(First In Last Out))방식을 사용하는 자료구조.

Top이라는 포인터를 지정해 위치를 설정함.

stack의 작동 원리

• Push()
  스택에 원소를 추가한다.
• Pop()
  스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
• Top()
  스택 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다.)
• IsEmpty()
  스택이 비어있다면 True, 비어있지 않으면 False를 반환한다

2.큐

후입선출(FIFO(First In First Out))방식을 사용하는 자료구조

Front포인터를 두어 제거 연산을, Rear 포인터를 두어 입력 연산을 담당함. 

queue의 작동 원리

• Push()
  큐에 원소를 추가한다.
• Pop()
  스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
• IsEmpty()
  큐가 비어있다면 True, 비어있지 않으면 False를 반환한다

3.재귀함수

말 그대로 자기 자신을 호출하는 함수를 의미한다.

가장 대표적인 예시인 팩토리얼을 재귀로 구현한 방식과 재귀를 이용하지 않은 방식으로 표현하면

//재귀를 이용한 방식
int factorial(int n) { 
    if (n === 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

//재귀를 이용하지 않은 방식
int factorial_nonrecursive(int n) {
	result = 1
    for i in range(1,n+1):
    	result *=i
    return result
}

재귀를 이용한 방식이 코드가 짧고 간편하다.

따라서, 재귀함수는 변수를 여럿 만들 필요가 없고 반복문을 사용하지 않아도 되기에 간결한 코드가 된다는 장점이 있으나연속적으로 함수를 호출하면서 지역변수, 매개변수, 반환값을 stack에 저장하며 지연이 생긴다는 단점도 있다.

장점

 

1. 가독성: 코드가 더 직관적이고 읽기 쉬우며 변수를 여러개 만들 필요가 없다.
2. 문제 해결이 편함: 재귀식을 그대로 가져오면 되기 때문에 문제 해결에 대한 접근을 손쉽게 얻을 수 있다.

단점

1. 성능: 지속적인 함수 호출로 호출 스택에 작업이 지속적으로 추가되어 성능 저하가 발생할 수 있다.

이런 식으로 반복되는 값에 대한 예외 처리가 없는 경우도 성능 저하 발생 가능

4. 그래프

노드와 간선으로 이루어진 자료구조를 말한다.

• 노드(Node) : 데이터를 저장하는 위치, 정점(Vertex)라고도 함.
• 간선(Edge) : 노드와 노드, 정점과 정점을 연결하는 선

보통 그래프를 표현하는 방식은 인접 행렬 방식과 인접 리스트 방식으로 나뉨

인접 행렬(Adjacency Matrix) 방식

2차원 배열로 그래프의 연결 관계를 표현하는 방식

연결이 되어있지 않은 노드끼리는 무한의 비용/0으로 가정함.

모든 관계를 저장하기 때문에 노드 개수가 많을수록 메모리가 낭비됨

인접 리스트(Adjacency List) 방식

'연결 리스트'라는 자료구조를 이용해 구현(C++/Java), 파이썬은 기본 리스트 라이브러리 사용 가능

리스트로 그래프의 연결 관계를 표현하는 방식

두 개의 노드가 연결되어있는지 확인하는 과정이 필요해 정보를 얻는 속도가 느림

인접 행렬과 인접 리스트 방식

DFS(Depth-First-Search)

말 그대로 깊이 우선 탐색 방식을 의미한다.

구현 시 대부분 재귀함수를 이용한다.

아래 그림과 동작 과정,코드를 통해 이를 이해해보자

 

일반적으로 DFS의 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리.
   방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

DFS 동작 방식 GIF

보통 코딩테스트/문제에서는 관행적으로 번호가 낮은 순으로 처리하기에 정렬의 필요성 존재.

def dfs(graph,v,visited):
	visited[v] = True
    print(v,end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph,i,visited)

graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited=[False]*9
dfs(graph,1,visited)

dfs의 예시는 다음과 같으며, 보통 visited 행렬을 따로 만들어 사용하는 경우가 많다.

 

보통 DFS는 다음과 같은 상황에 사용한다.

• 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제(조합, 순열)
• 단순히 두 지점 간의 경로가 존재하는지 여부를 찾는 문제(조건문 넣으면 중간에 종료 가능) => 백트래킹

BFS(Breadth-First-Search)

말 그대로 너비 우선 탐색 방식을 의미한다.

보통 선입선출 방식인 큐 자료구조를 이용해서 구현한다.

아래 그림과 동작 과정,코드를 통해 이를 이해해보자

 

일반적으로 BFS의 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를
   모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS 동작 방식 GIF

from collections import deque

def bfs(graph,start,visited):
	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

graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited=[False]*9
bfs(graph,1,visited)

bfs의 예시는 다음과 같으며, 보통 visited 행렬을 따로 만들어 사용하는 경우가 많다.

보통 BFS는 다음과 같은 상황에 사용한다.

•  최단경로 문제를 풀어야할때 => 제일 많이 사용
• 그래프의 깊이가 깊지 않을 경우