탐색 알고리즘(DFS, BFS)과 활용

1. DFS, BFS의 기본 개념

 

깊이 우선 탐색(DFS)

탐색을 하고자 하는 그래프상에서, 깊이를 우선적으로 탐색하는 기법

• 현 경로상의  노드를  기억하기  때문에  적은  메모리를  사용한다.
• 찾으려는  노드가  깊은  단계에  있는  경우  BFS 보다  빠르게  찾을  수  있다.

*참고

탐색에서는 중복된 상태를 막기 위하여 2개의 리스트를 사용한다.

OPEN 리스트: 확장은 되었으나 아직 탐색하지 않은 상태들이 들어있는 리스트

CLOSED 리스트: 탐색이 끝난 상태들이 들어있는 리스트

 

closed 리스트: 방문 완료를 나타내는 배열(visited) 사용

open 리스트: 탐색할 대상을 stack에 넣어서 사용 (혹은, 재귀를 활용해서 구현)

 

void dfs(int node) {
	visited[node] = true;
    cout << node << " ";
    for (int i = 0; i < a[node].size(); i++) {
    	int next = a[node][i];
        if (visited[next] == false)
        	dfs(next);
    }
}

 

 

너비 우선 탐색(BFS) 

탐색을 하고자 하는 그래프상에서, 너비를 우선적으로 탐색하는 기법

• 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어져도 답을 찾을 수 있다.

 

closed 리스트: 방문 완료를 나타내는 배열(visited) 사용

open 리스트: 탐색할 대상을 queue에 넣어서 사용

 

void bfs(int start) {
    queue<int> q;
    visited[start] = true;
    q.push(start);
    while (!q.empty()) {
    	int node = q.front();
        q.pop();
        cout << node << " ";
        for (int i = 0; i < a[node].size(); i++) {
        	int next = a[node][i];
            if (visited[next] == false) {
            	visited[next] = true;
                q.push(next);
            }
    	}
    }
}

 

2. BFS에서 visited 배열의 활용

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

BFS에서 유명한 토마토 문제를 살펴보자.

 

이 문제를 풀 때 생각해야하는 점은 다음과 같다.

 

1. 출발점으로 부터의 거리 구하기(시간이 얼마나 지나서 토마토가 익었는지)

2. 시작할 때 익어있는 토마토는 하나가 아니다.

3. 토마토의 다음 토마토는 상하좌우에 있다.

 

하나씩 살펴보자!

 

1. 출발점으로 부터의 거리 구하기(시간이 얼마나 지나서 토마토가 익었는지)

시간이 얼마나 걸렸는지 체크하는 배열을 만들면 쉽게 해결할 수 있다.

이차원 time[][] 배열을 만들어서 해결했다.

time[next_x][next_y] = time[x][y] + 1;

 

 

2. 시작할 때 익어있는 토마토는 하나가 아니다.

익어있는 토마토를 한꺼번에 큐에 넣고 시작하자.

큐를 미리 만들어두고, 입력을 받을 때 토마토가 익어있다면 큐에 넣어주도록 하자!

 

3. 토마토의 다음 토마토는 상하좌우에 있다.

다음 노드로 가기 쉽게 상하좌우 이동배열을 활용하자.

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int M, N;
void bfs();
int v[1001][1001];
int time[1001][1001] = { 0, }; 
queue <pair<int, int>> q; // pair은 토마토의 위치
int dx[4] = { -1,1,0,0 }; // 상하좌우로 이동하기
int dy[4] = { 0,0,-1,1 };

int main() {
	int max = 0;
	cin >> M >> N;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			cin >> v[i][j];
			if (v[i][j] == 1) {
				q.push(make_pair(i, j));
			}
		}
	}
	bfs();
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			if (v[i][j] == 0) {
				cout << -1;
				return 0;
			}
			if (max < time[i][j]) max = time[i][j];
		}
	}
	cout << max;
}

void bfs() {
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0;i < 4;i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];

			if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M && (v[next_x][next_y]==0)) {
				v[next_x][next_y] = 1;
				q.push(make_pair(next_x, next_y));
				//------레벨----------
				time[next_x][next_y] = time[x][y] + 1;
			}
		}
	}
}

 

활용할 수 있는 문제 추천

BOJ 5014 스타트링크

 

3. DFS로 사이클 찾기

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

 

dfs를 활용하여 그래프에서 사이클을 찾아보자!

 

그래프에서 사이클이 생기는 경우는 다음 그림과 같다.

 

그림에서 노드 u는 재귀적으로 다음 노드를 탐색하는 중, 다시 노드u로 통하는 간선(빨간색 선)을 발견했다.

노드 v의 관점으로 바라보면, 노드 u는 이미 방문한 상태이지만 아직 dfs 호출이 끝나지 않았다.

이를 활용하면 dfs에서 사이클을 찾을 수 있다!

 

이처럼 어느 출발점 u에서 시작된 dfs(u)가 종료되기 전에 u로 향하는 간선이 발견된다면,
그래프에 사이클이 있다는 것을 의미한다.

 

코드로 좀 더 살펴보자.

 

방문한 노드를 나타내는 visited[] 배열과 dfs호출이 끝났는지 확인하는 finished[] 배열을 만들었다.

void dfs(int node) {
	visited[node] = true; // 노드 방문을 체크한다.
	int next = v[node];
    
	if (!visited[next])
		dfs(next);
	else if (!finished[next]) {// 만약 다음 노드가 방문한 상태이고, 종료되지 않은 노드라면 사이클 발생
		cnt++;
	}
	finished[node] = true; // 노드의 dfs 종료를 체크한다.
}

 

전체 코드

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;

void dfs(int node);
void init();
int cnt = 0;
int v[1001];
bool visited[1001];
bool finished[1001];

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1;i <= n;i++) {
			cin >> v[i];
		}
		for (int i = 1;i <= n;i++) {
			if (!visited[i]) dfs(i);
		}
		cout << cnt << "\n";

		init();

	}
}

void dfs(int node) {
	visited[node] = true;
	int next = v[node];
	if (!visited[next])
		dfs(next);
	else if (!finished[next]) {//사이클 발생
		cnt++;
	}
	finished[node] = true;
}

void init() {
	cnt = 0;
	memset(v, 0, 1001);
	memset(visited, false, 1001);
	memset(finished, false, 1001);
}

 

활용할 수 있는 문제 추천

BOJ 2668 숫자 고르기

사이클이 생겼을 때 for 문으로 다시 한바퀴 돌면서 사이클에 포함되는 노드의 개수와 리스트를 저장하면 해결할 수 있다.

BOJ 9466 텀 프로젝트