알고리즘 - 그래프 탐색(dfs,bfs)위한 기초지식. 스택/큐/그래프

*참고저서 <이것이 취업을 위한 코딩테스트다>

 

dfs, bfs 로 불리는 그래프 탐색 문제는 코딩 테스트의 단골 출제 유형이다.

자료구조에 대한 이해가 어느정도는 필요한 영역으로서 

스택 / 큐 / 그래프에 대해 알아야만 한다.

이에 대해 아주 간단히 살펴보려한다.

 

1. 스택(stack)

  기초 자료구조 중의 하나로 선입후출의 구조를 띄고 있다.

선입후출이란 먼저 들어간 자료가 가장 늦게 빠져나오는 것을 뜻한다.

 

파이썬에서는 기본 제공메서드인 append로 삽입 연산을, pop으로 삭제 연산을 실행할 수 있다.

 

재귀(recursion)에 대해 이미 알고 있다면, 재귀가 스택의 형태로 처리된다는 것도 알아야 한다.

 

 

2. 큐(queue)

  스택과 다르게 선입선출의 구조를 띄고 있는 자료구조이다. 

역시 삽입 연산과 삭제 연산으로 이루어져 있지만, 그 방법이 같지 않다.

 

파이썬에서 제공하는 deque 라이브러리의 사용이 필요하다.

변수명 = deque() 와 같은 형태로 생성하여, append로 삽입, popleft로 삭제 연산을 수행한다.

 

3. 그래프(graph)

  그래프는 기본적으로 '노드(정점)'과 '에지(간선)'으로 구성되어 있다. 각 노드들을 에지들이 연결하고 

있는 형태라고 보면 된다. 에지로 연결된 노드들을 '인접하다'라고 말한다.

 

그래프의 표현 방식은 크게 두 가지이다.

1) 인접 행렬

  좀더 직관적인 형태로 n개의 정점에 대해 n^2만큼의 2차원 배열을 만들어

노드가 존재하면 1, 아니면 0으로 표기한다.(가중치가 있는 그래프일 시 가중치를 표기한다.)

 

위 사진의 그래프를 왼쪽 노드부터 0,1,2로 말한다면 인접 행렬은 다음과 같다.

0 1 0

1 0 1

0 1 0

 

2) 인접 리스트

  인접 행렬이 항상 n^2만큼의 메모리를 사용하는 반면 인접 리스트의 경우 에지 수만큼만 저장하기에

좀 더 효율적인 방식이라 할 수 있다. 각 노드들마다 리스트를 지니고 있고 인접한 노드들의 인덱스들이

값이 된다.

 

위 그래프를 인접 리스트로 표현하며 다음과 같다.

[1]

[0,2]

[1]