비선형구조란 번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 여러 개의 원소가 존재하는 탐색구조를 말한다. 일반적으로 자료가 트리나 그래프로 구 성되어 있을 경우를 비선형구조라 하고 이러한 트리나 그래프의 모든 정점을 탐색하는 것 을 비선형 탐색이라고 이해하면 된다.
비선형구조는 선형과 달리 자료가 순차적으로 구성되어 있지 않으므로 단순히 반복문을 이용하여 탐색하기에는 어려움이 있다. 그러므로 비선형구조는 스택이나 큐와 같은 자료구 조를 활용하여 탐색하는 것이 일반적이다.
비선형구조의 탐색은 크게 깊이우선탐색(depth first search, dfs)과 너비우선탐색 (breadth firth search, bfs)으로 나눌 수 있으며, 이 두 가지 탐색법을 활용한 다양한 응용 이 있으나 이 교재에서는 기본적인 두 가지 탐색법에 대해서 익히도록 한다.
- 비선형구조
비선형구조의 탐색을 다루기 전에 그래프와 트리에 대해서 간단히 알아보자. 트리와 그 래프를 이루는 기본 요소를 정점(vertex)과 간선(edge)이라고 한다.
원은 정점, 선분은 간선을 나타내며, 는 보통간선, 는 방향간선, 는 가중치가 15 인 양방향통행 간선, 는 가중치가 7인 일방통행 간선(방향간선)을 나타낸다.
정점은 점 또는 원으로 표현하며, 일반적으로 상태나 위치를 표현한다. 간선은 정점들을 연결하는 선으로 표현하며, 정점들 간의 관계를 표현한다.
- 경로(path)와 회로(cycle)
그래프에서 임의의 정점 s에서 임의의 정점 t로 이동할 때, s에서 t로 이동하는데 사용한 정점들을 연결하고 있는 간선들의 순서로 된 집합을 경로라고 한다. 회로는 그래프에서 임 의의 정점 s에서 같은 정점 s로의 경로들을 말한다.
왼쪽의 빨간 간선들은 s에서 t로의 경로를 나타내고, 오른쪽의 빨간 간선들은 s에서 t로의 회로를 나타낸다.
- 자기간선(loop)과 다중간선(multi edge)
임의의 정점에서 자기 자신으로 연결하고 있는 간선을 자기간선, 임의의 정점에서 다른 정점으로 연결된 간선의 수가 2개 이상일 경우를 다중간선이라고 한다.
왼쪽은 자기간선 오른쪽은 다중간선을 나타낸다.
- 그래프의 차수(degree)
그래프의 임의의 한 정점에서 다른 정점으로 연결된 간선의 수를 차수라고 한다. 다음
그림은 각 정점에 대한 차수를 나타낸다.
각 정점에서의 차수
- 그래프의 구현
그래프를 구현하는 방법은 인접행렬(adjacency matrix)과 인접리스트(adjacency list)로 크게 나눌 수 있다.
일반적으로 정보올림피아드를 비롯한 프로그래밍 대회에서 그래프는 정점의 수, 간선의 수, 각 간선들이 연결하고 있는 정점 2개로 이루어진 정보가 주어지는 경우가 대부분이다.
다음은 실제로 그래프가 주어질 때, 이를 저장하는 2가지 방법을 보여준다.
7개의 정점과 11개의 간선을 가지는 가중치 그래프의 예
이러한 그래프의 경우 일반적인 입력데이터의 형식은 다음과 같다.
입력 형식 입력데이터의 예
첫 번째 줄에 정점의 수 n과 간선의 수 m 이 공백으로 구분되어 입력된다.
두 번째 줄부터 m개의 줄에 걸쳐서 간선으 로 연결된 두 정점의 번호와 가중치가 공백으 로 구분되어 입력된다.
7 11 1 2 47 1 3 69 2 4 57 2 5 124 3 4 37 3 5 59 3 6 86 4 6 27 4 7 94 5 7 21 6 7 40
[표-2] 그래프의 대표적인 입력형식과 입력데이터의 예
- 인접행렬의 구현
[표-2]의 입력예시를 인접행렬로 받기 위해서는 2차원 배열을 이용한다. 먼저 최대 정점 의 수에 맞추어 2차원 배열을 선언하고 각 배열의 칸에 연결된 정보를 저장한다. 앞 그래 프를 2차원 행렬을 이용하여 다음과 같이 저장한다.
왼쪽은 가중치가 없는 표현, 오른쪽은 가중치가 있는 표현이다. 예를 들어, 3행 4열의 경우 왼쪽은 1, 오른쪽은 37이 기록되어 있다. 왼쪽의 1은 간선이 있음을 의미하고, 오른쪽은
간선이 있을 때 가중치를 저장한다.
2차원 행렬을 이용하여 저장하는 소스코드는 다음과 같다. 단 최대 정점의 수는 100개 로 가정한다.
줄 코드 참고 1
2 3 4 5 6 7 8 9 10 11 12 13 14
#include <stdio.h>
int n, m, G[101][101];
int main() {
scanf("%d %d",&n,&m);
for(int i=0; i<m; i++) {
int a, b, w;
scanf("%d %d %d", &a, &b, &w);
G[a][b]=G[b][a]=w;
} }
10: 정점 a, b를 연결하는 간선, w 는 가중치 12: 만약 가중치 가 없다면 1,방향 간선이면G[a][b]
만 저장.
- 인접리스트의 구현
인접행렬로 표현할 때에는 연결되지 않았던 부분까지 모두 표현이 된다. 즉, 각 칸에 0 이라고 기록된 부분은 연결이 되지 않은 부분을 의미한다. 사실 일반적인 그래프에서 행렬 상에서 0이라고 표현되는 부분이 많을 가능성이 크다.
알고리즘을 구현할 때에도 이 0이라고 표시된 부분까지 모두 조사를 해야 하므로 효율 이 떨어지는 경우가 많다. 이러한 단점을 극복하기 위하여 제안된 방법이 인접리스트이고 이 방법은 인접행렬에서 0으로 표시된 부분은 저장하지 않으므로 효율을 높이고 있다.
[그림-10] 그래프의 인접리스트 표현
[그림-11] 가중치 그래프의 인접리스트 표현
[표-2]의 입력 예시를 인접리스트로 구현하기 위해서는 [그림-10], [그림-11]과 같이 연결리스트로 구현할 수 있지만 STL에서 제공하는 std::vector()를 이용하여 간단하게 구 현할 수 있다. [표-2]의 입력예시를 인접리스트로 구현하면 다음과 같은 그림이 된다.
인접리스트에서는 정점과 가중치의 쌍으로 간선이 있는 것만 연결한다.
예를 들어 1행의 경우 1-2로의 간선의 가중치는 47이고 1-3으로의 간선의 가중치는 69라는 의미이다.
std::vector()를 이용한다면 위와 같이 인접행렬로 구현하는 것보다 공간을 적게 사용한 다. 따라서 전체탐색법을 구현할 때, 당연히 탐색시간도 줄일 수 있다. 계산량으로 표현하 자면, 인접행렬로 모든 정점을 탐색하는데 의 시간이 드는데 반해, 인접리스트로 표현하면 의 시간이 든다.
여러 가지 장점이 있기 때문에 대회에서는 주로 인접리스트를 이용한 방법을 활용하는 경우가 많으므로 반드시 익혀둘 수 있도록 한다.
- 깊이우선탐색(dfs)
그래프 중 회로(cycle)가 없는 그래프를 트리라고 한다. [그림-13]은 트리를 나타낸다.
이 트리의 가장 위에 있는 정점에서 출발하여 모든 정점들을 깊이우선으로 탐색하며, 탐색 하는 순서를 알아보자.
10개의 정점(vertex)과 9개의 간선(edge)을 가진 트리
출발 정점을 트리의 가장 위에 있는 정점으로 하고, 한 정점에서 이동 가능한 정점이 여 러 개 있을 경우 왼쪽의 정점부터 방문한다고 가정하면, 단계별 탐색 과정은 다음과 같다.
깊이우선 1~3 단계
깊이우선탐색과정에서 3단계 이후 더 이상 진행할 수 있는 정점이 없다. 그 이유는 간선 으로 연결된 정점들 중 아직 방문하지 않은 정점을 방문하기 때문이다.
이처럼 더 이상 진행할 수 없을 때는 다시 이전 정점으로 되돌아가는 과정이 필요하다.
일반적으로 이 과정을 백트랙(backtrack)이라고 한다. 백트랙은 비선형구조의 탐색에서 매 우 중요하다. 백트랙은 스택(stack)이나 재귀함수(recursion)를 이용하면 쉽게 구현할 수 있다.
깊이우선 4 ~ 6 단계
4, 5, 6단계는 연속으로 백트랙이 발생한다. 이는 더 이상 진행할 수 없는 정점까지 도달 했다는 것을 의미한다. 계속 해서 다음 단계로 진행하는 과정은 다음과 같다.
깊이우선 7~9 단계
위 단계에서 마지막 정점을 방문하면 깊이우선탐색이 완료된다.
탐색종료
깊이우선탐색을 정리하여 설명하면 먼저 시작 정점에서 간선을 하나 선택하여 진행할 수 있을 때까지 진행하고 더 이상 진행할 수 없다면 백트랙하여 다시 다른 정점으로 진행 하여 더 이상 진행할 정점이 없을 때까지 이 과정을 반복하는 탐색법으로, 간선으로 연결 된 모든 정점을 방문할 수 있는 탐색법이다.
깊이우선탐색의 알고리즘은 다음과 같다. 이 탐색법은 백트래킹(backtracking)이라는 알 고리즘 설계 기법의 중심이 되며 백트래킹 기법은 모든 문제를 해결할 수 있는 가장 기본 적인 방법이므로 꼭 익혀둘 필요가 있다.
줄 코드 참고
1 2 3 4 5 6 7 8 9 10 11
bool visited[101];
void dfs(int k) {
for(int i=0; i<G[i].size(); i++) if(!visited[G[k][i].to]) {
visited[G[k][i].to]=true;
dfs(G[k][i]);
}
return;
}
1: 방문했는지 체 크해 두는 배열 4: 정점 k와 연 결된 모든 정점 방문
5: 만약 아직 방 문하지 않았으면 7: 방문했다고 체 크하고
8: 깊이우선탐색 진행
10: 더 이상 갈 길 이 없으면 backtrack
이 방법은 그래프를 인접리스트에 저장했을 경우에 활용할 수 있다. 이 방법은 전체를 탐색하는데 있어서 반복문의 실행횟수는 모두 번이 된다. 따라서 일반적으로 속도가 더 빠르기 때문에 자주 활용된다.
만약 인접행렬로 그래프를 저장했다면 다음과 같이 작성하면 된다.
줄 코드 참고
1 2 3 4 5 6 7 8 9 10
bool visited[101];
void dfs(int k) {
for(int i=1; i<=n; i++)
if( G[k][i] && !visited[G[k][i]] ) {
visited[G[k][i]] = true;
dfs(G[k][i]);
}
return;
1: 방문했는지 체 크해 두는 배열 4: 모든 정점에 대해서 검사 5: k에 연결되어 있으면서, 아직 방 문하지 않았으면 7: 방문했다고 체 크하고
8: 깊이우선탐색 진행
10: 더 이상 갈 길
이 방법은 전체를 탐색하는데 있어서 반복문을 번 실행하게 된다. 따라서 평균적으로 인접리스트보다 느리지만 구현이 간편하므로, 값이 크지 않은 문제라면 충분히 적용할 가치가 있다.
문제 1
두더지 굴(S)
정올이는 땅속의 굴이 모두 연결되어 있으면 이 굴은 한 마리의 두더지가 사는 집 이라는 사실을 발견하였다.
정올이는 뒷산에 사는 두더지가 모두 몇 마리인지 궁금해졌다. 정올이는 특수 장 비를 이용하여 뒷산의 두더지 굴을 모두 나타낸 지도를 만들 수 있었다.
이 지도는 직사각형이고 가로 세로 영역을 0 또는 1로 표현한다. 0은 땅이고 1은 두더지 굴을 나타낸다. 1이 상하좌우로 연결되어 있으면 한 마리의 두더지가 사는 집으로 정의할 수 있다.
[그림 1] [그림 2]
[그림 2]는 [그림 1]을 두더지 굴로 번호를 붙인 것이다. 특수촬영 사진 데이터를 입 력받아 두더지 굴의 수를 출력하고, 각 두더지 굴의 크기를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 가로, 세로의 크기를 나타내는 n이 입력된다.(n은 30이하의 자연수) 두 번째 줄부터 n줄에 걸쳐서 n개의 0과 1이 공백으로 구분되어 입력된다.
출력
첫째 줄에 두더지 굴의 수를 출력한다. 둘째 줄부터 각 두더지 굴의 크기를 내림 차순으로 한 줄에 하나씩 출력한다.
입력 예 출력 예
7
0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0
3 9 8 7