탐색 알고리즘에 대해서 알아볼 것이다. 그래프의 탐색의 목적은 모든 정점을 1번씩 방문 하는 것이다.
DFS (깊이 우선 탐색)
깊이 우선 탐색은 한 방향으로 갈 수 있는 만큼 깊이가기때문에 깊이 우선 탐색이다. 일반적으로 DFS 탐색방법에서는 스택(stack)자료구조를 이용한다.
백트래킹(Backtracking)
탐색 과정에서 무한히 깊이가는 것을 방지하기 위해서 깊이제한(depth bound)을 둔다. depth bound에 도달할 때까지 목표(노드)가 발견되지 않으면 그 전에 탐색한 노드의 부모 노드로 되돌아온다. 이렇게 되돌아 오는 과정을 **백트래킹(Backtracking)**이라 한다.
탐색과정
최대한 깊숙히 많은것을 탐색할 때 사용하며, 스택을 사용한다.
스택을 이용해 갈 수 있는 만큼 최대한 많이가고, 갈 수 없으면 이전 정점으로 돌아온다.(백트랙킹)
방문한 곳은 표시를 해둔다.(check[i] )
이미 방문한 곳은 건너띄고, 갈 수 있는 곳으로 간다. 스택이 비워질 때까지 계속 pop을 한다. 스택이 비어있으면 DFS탐색이 종료된다.
장단점
장점
현재 경로상의 노드들만 기억하면 되므로 저장공간의 소요가 비교적 적다.
목표노드가 깊은 단계에 있을 경우에 해를 빨리 구할 수 있다.
단점
해가 없는 경로에 너무 깊이 빠지게 될 가능성이 잇다. 따라서 실제 경우에는 미리 지정한 임의의 깊이(depth bound)까지만 탐색하고 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 것이 유용할 수 있다.
얻어진 경로가 최단 경로가 아닐 수 있다. 목표까지의 경로가 여러개인 문제에 대해서 DFS는 목표에 도달하면 탐색을 종료하므로, 이때 찾은 경로는 최적의 경로가 아닐 수 있다.
구현
그래프가 disconnected이거나 혹은 방향 그래프라면 DFS에 의해서 모든 노드가 방문되지 않을 수 있다.
슈도코드
DFS(G, v) visited[v] <- yesfor each node adjacent to x doif visited[v] = NO thenDFS(G, u); endend
인접행렬 구현
dfs(x)는 x를 방문했다는 의미이다. 재귀 호출을 이용해서 구현할 수 있다.
voiddfs(int x){check[x] =true; //방문한 것 표시printf("%d ",x); //다음 정점 방문for(int i=1;i<=n;i++){ //간선이 있고, 방문을 하지 않았을 경우if(a[x][i]==1&&check[i]==false) dfs(i); }}
voiddfs(int x){check[x] =true; //방문한 것 표시printf("%d ",x); //다음 정점 방문 // a[x]는 x와 연결된 정점이다.for(int i=1;i<a[x].size();i++){int y =a[x][i];if(check[y]==false)dfs(y); }}
현재 정점에서 깊이가 1인 정점을 모두 탐색한 뒤 깊이를 늘려가는 방식이다. 너비우선탐색은 백트랙을 하지 않는다. 대신에 현재 정점에서 깊이가 1인 정점을 모두 방문해야하므로 **큐(queue)**라는 FIFO(First In First Out)자료구조를 활용해 현재 정점에서 깊이가 1 더 깊은 모든 정점을 순차적으로 큐에 저장해 탐색에 활용한다.
std::queue()를 활용하는 방법을 익힐 필요가 있다.
BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다.
탐색과정
L0 = {s}, s는 출발 노드
L1 = L0의 모든 이웃 노드들
L2 = L1에서 모든 이웃들 중 L0에 속하지 않는 노드들
...
LN = Ln에서 모든 이웃들 중 Ln-1에 속하지 않는 노드들
다음과 같은 순서로 방문하는 방법이다.
Queue
최대한 넓게 가는길을 탐색할 때 사용하며, 큐를 사용한다. 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식이다.
BFS는 큐에 넣을 때 방문했다고 체크(check[i])해야한다.
큐에서 pop한 노드들 중에서 방문하지 않은 모든 이웃 노드를 큐에 넣으면서 방문했다고 체크해준다.
Queue가 빌때까지 진행해준다.
구현
그래프가 disconnected이거나 혹은 방향 그래프라면 BFS에 의해서 모든 노드가 방문되지 않을 수 있다.
슈도코드
BFS(G, s)// 그래프 G와 출발 노드 s Q <- ø; // 큐를 하나 생성Enqueue(Q,s);while Q!=ø do u <-Dequeue(Q)for each v adjacent to u doif v is unvisited then mark v is visited;Enqueue(Q,v); end; end; end;
BFS(G, s)// 그래프 G와 출발 노드 s Q <- ø; d[v]<-0; π[v]<-null;Enqueue(Q,s);while Q!=ø do u <-Dequeue(Q)for each v adjacent to u doif v is unvisited then //일반적으로 방문하지 않은 것은 -1로 넣어두고 구한다. mark v is visited; d[v]<-d[u]+1; π[v]<-u;Enqueue(Q,v); end; end; end;
// 최단경로 출력PRINT-PATH(G,s,v)if v=s then print s;elseif π[v] = null then print "no path from s to v exists"; else PRINT-PATH(G,s,π[v]); print v; end.
n*n체스 보드판에 n개의 queen을 서로 공격하지 못하도록 배치하는 방법을 찾아내는 문제. 대각선 검사하면서 가야하는 알고리즘에 유용하다.
퀸은 8방향으로 모두 공격할 수 있다.
첫 번째 행, 첫 번째 열에 퀸을 놓는다.
다음 행에서 가능한 가장 왼쪽 열에 퀸을 놓는다.
n번째 열에 더 이상 퀸을 놓을 수 없다면 백트랙한다.
마지막 행에 퀸을 놓으면 하나의 해를 구한 것이다.
모든 경우를 조사할 때까지 백트래킹해가며 해들을 구한다.
깊이우선탐색을 하며 해를 구할 때마다 카운트해 원하는 해를 구할 수 있다. 열과 대각선만 검사하면 된다. 대각선은 행+열 위치에 체크해 기울기가 증가하는 대각선 상에 퀸을 놓을 수 있는지 없는지 확인한다. 기울기가 감소하는 대각선은 행과 열의 차가 일정하다. n+(행-열)의 위치에 체크. 백트랙 시에 가장 중요한 점은 체크배열에 기록해 두었던 체크를 모두 해제해야한다.