[C++] 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search)

깊이 우선 탐색은 한 방향으로 계속 가다가 더 이상 갈 수 없으면 부모 노드로 돌아와 다른 방향으로 탐색한다.

• 주로 Stack이나 재귀 함수를 이용해 구현한다.
• 모든 노드를 방문하거나 가중치, 이동 과정에 제약이 있을 경우에 사용하면 좋다.
• 자기 자신을 호출하는 순환 알고리즘의 형태를 갖고 있다.
• BFS보다 좀 더 간단하나 단순 검색 속도 자체는 BFS보다 느리다.

DFS

 

너비 우선 탐색은 현재 노드에서 가장 가까운 노드를 먼저 방문해 탐색한다.

• 주로 Queue를 이용해 구현한다.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾는 경우에 사용하면 좋다.

 

BFS

 

기본 원리

 

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

1260번: DFS와 BFS

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

vector<int> graph[1001]; // 연결 그래프
bool checked[1001]; // 방문 체크

void DFS(int start)
{
	checked[start] = true;
	cout << start << " ";
	for (int i = 0; i < graph[start].size(); i++)
		if (!checked[graph[start][i]])
			DFS(graph[start][i]);
}

void BFS(int start)
{
	queue<int> q;
	q.push(start);
	checked[start] = true;
	while (!q.empty()) {
		int val = q.front();
		cout << val << " ";
		q.pop();
		for (int i = 0; i < graph[val].size(); i++)
			if (!checked[graph[val][i]]) {
				q.push(graph[val][i]);
				checked[graph[val][i]] = true;
			}
	}
}

int main()
{
	int N, M, V;
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for (int i = 1; i <= N; i++)
		sort(graph[i].begin(), graph[i].end());

	fill_n(checked, N + 1, false);
	DFS(V);
	cout << "\n";
	fill_n(checked, N + 1, false);
	BFS(V);
}

 

문제 : DFS

 

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

2667번: 단지번호붙이기

#include <iostream> 
#include <set> 
using namespace std;

int n;
bool map[25][25], checked[25][25];

int DFS(int y, int x)
{
	if (0 > y || y >= n || 0 > x || x >= n)
		return 0;
	if (checked[y][x] || !map[y][x])
		return 0;
	checked[y][x] = true;
	return 1 + DFS(y, x + 1) + DFS(y, x - 1) + DFS(y + 1, x) + DFS(y - 1, x);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			scanf("%1d", &map[i][j]);

	multiset<int> s;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (map[i][j] && !checked[i][j])
				s.insert(DFS(i, j));

	cout << s.size() << "\n";
	for (int i : s)
		cout << i << "\n";
}

 

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

2606번: 바이러스

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

int ans = -1;
vector<int> graph[101];
bool checked[101];

void DFS(int start) {
	ans++;
	checked[start] = true;
	for (int i = 0; i < graph[start].size(); i++)
		if (!checked[graph[start][i]])
			DFS(graph[start][i]);
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	DFS(1);
	cout << ans;
}

 

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

2636번: 치즈

#include <iostream>
using namespace std;

int N, M;
int time, piece, cnt;
bool map[100][100], check[100][100];
int dir[4][2]{ {1,0},{-1,0},{0,1},{0,-1} };

void DFS(int x, int y)
{
	check[y][x] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0], ny = y + dir[i][1];

		if (nx < 0 || nx >= M || ny < 0 || ny >= N)
			continue;
		if (check[ny][nx])
			continue;

		if (map[ny][nx]) {
			cnt--;
			map[ny][nx] = false;
			check[ny][nx] = true;
		}
		else
			DFS(nx, ny);
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j])
				cnt++;
		}

	while (cnt) {
		time++;
		piece = cnt;

		DFS(0, 0);

		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				check[i][j] = false;
	}

	cout << time << "\n" << piece;
}

 

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

14888번: 연산자 끼워넣기

#include <iostream>
using namespace std;

int n; int num[11]; int oper[4];
int mmin = 1000000000, mmax = -1000000000;

void DFS(int idx, int result, int hap, int cha, int gop, int na)
{
	if (hap < 0 || cha < 0 || gop < 0 || na < 0) return;

	if (idx == n) {
		if (result > mmax) mmax = result;
		if (result < mmin) mmin = result;
		return;
	}

	DFS(idx + 1, result + num[idx], hap - 1, cha, gop, na); // +연산
	DFS(idx + 1, result - num[idx], hap, cha - 1, gop, na); // -연산
	DFS(idx + 1, result * num[idx], hap, cha, gop - 1, na); // *연산
	DFS(idx + 1, result / num[idx], hap, cha, gop, na - 1); // /연산
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> num[i];
	for (int i = 0; i < 4; ++i)
		cin >> oper[i];

	DFS(1, num[0], oper[0], oper[1], oper[2], oper[3]);
	cout << mmax << "\n" << mmin;
}

 

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

9466번: 텀 프로젝트

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

int team;
vector<int> v;
vector<bool> check, visited; // 방문, 재방문

void DFS(int start, int index)
{
	if (visited[index]) {
		team++;

		int temp = v[index];
		while (temp != index) {
			team++;
			temp = v[temp];
		}
	}
	else {
		visited[index] = true;
		if (!check[v[index]]) {
			DFS(start, v[index]);
			check[index] = true;
		}
	}
}

int main()
{
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;

		team = 0;
		v = vector<int>(N + 1, 0);
		check = vector<bool>(N + 1, false);
		visited = vector<bool>(N + 1, false);

		for (int i = 1; i <= N; i++)
			cin >> v[i];

		for (int i = 1; i <= N; i++) {
			if (!check[i]) {
				visited = vector<bool>(N + 1, false);
				DFS(i, i);
			}
		}

		cout << N - team << "\n";
	}
}

 

문제 : BFS

 

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

2178번: 미로 탐색

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

bool map[100][100], ck[100][100];
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);

	int ans = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	ck[0][0] = true;
	while (!q.empty()) {
		ans++;

		int s = q.size();
		while (s--) {
			int tx = q.front().second, ty = q.front().first;
			q.pop();

			if (tx == m - 1 && ty == n - 1) {
				cout << ans;
				return 0;
			}

			for (int i = 0; i < 4; i++) {
				int nx = tx + dir[i][0], ny = ty + dir[i][1];
				if (nx < 0 || nx >= m || ny < 0 || ny >= n)
					continue;

				if (map[ny][nx] && !ck[ny][nx]) {
					q.push({ ny, nx });
					ck[ny][nx] = true;
				}
			}
		}
	}
}

 

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

2206번: 벽 부수고 이동하기

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

bool map[1000][1000], checked[1000][1000][2];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &map[i][j]);

	int answer = 0;
	queue<pair<int, pair<int, int>>> q;
	q.push({ 0, { 0, 0 } });
	checked[0][0][0] = true;
	while (!q.empty()) {
		answer++;

		int size = q.size();
		while (size--) {
			int tx = q.front().second.second;
			int ty = q.front().second.first;
			int crash = q.front().first;
			q.pop();

			if (tx == m - 1 && ty == n - 1) {
				cout << answer;
				return 0;
			}

			int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
			for (int i = 0; i < 4; i++) {
				int nx = tx + dir[i][0], ny = ty + dir[i][1];

				if (nx < 0 || nx >= m || ny < 0 || ny >= n)
					continue;
				if (checked[ny][nx][crash])
					continue;
				if (map[ny][nx]) {
					if (crash)
						continue;
					q.push({ 1,{ny, nx} });
				}
				else
					q.push({ crash,{ny, nx} });

				checked[ny][nx][crash] = true;
			}
		}
	}

	cout << -1;
}

 

 

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

7569번: 토마토

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

int map[100][100][100]{};
bool check[100][100][100]{};

int main()
{
	int M, N, H;
	cin >> M >> N >> H;

	queue<pair<int, pair<int, int>>> q;
	for (int i = 0; i < H; ++i)
		for (int j = 0; j < N; ++j)
			for (int k = 0; k < M; ++k) {
				cin >> map[i][j][k];

				if (map[i][j][k] == 1) {
					q.push({ i,{j,k} });
					check[i][j][k] = true;
				}
			}

	int answer = -1;
	while (!q.empty()) {
		++answer;

		int size = q.size();
		while (size--) {
			int tz = q.front().first;
			int ty = q.front().second.first;
			int tx = q.front().second.second;
			q.pop();

			int dir[9][3] = { {-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1} };
			for (int i = 0; i < 9; i++) {
				int nx = tx + dir[i][0], ny = ty + dir[i][1], nz = tz + dir[i][2];
				if (nx < 0 || nx >= M || ny < 0 || ny >= N || nz < 0 || nz >= H)
					continue;
				if (check[nz][ny][nx] || map[nz][ny][nx])
					continue;

				q.push({ nz,{ny, nx} });
				check[nz][ny][nx] = true;
				map[nz][ny][nx] = 1;
			}
		}
	}

	for (int k = 0; k < H; k++)
		for (int j = 0; j < N; j++)
			for (int i = 0; i < M; i++)
				if (!map[k][j][i]) {
					cout << -1;
					return 0;
				}
	cout << answer;
}

 

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

1697번: 숨바꼭질

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

bool checked[100001];

int main(void)
{
	int n, k;
	cin >> n >> k;

	int ans = -1;
	queue<int> q;
	q.push(n);
	checked[n] = true;
	while (!q.empty()) {
		ans++;

		int s = q.size();
		while (s--) {
			int x = q.front();
			q.pop();

			if (x == k) {
				cout << ans;
				return 0;
			}

			int dx[3] = { x + 1, x - 1, x * 2 };
			for (int i = 0; i < 3; i++)
				if (0 <= dx[i] && dx[i] <= 100000 && !checked[dx[i]]) {
					q.push(dx[i]);
					checked[dx[i]] = true;
				}
		}
	}
}

 

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

1726번: 로봇

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

int M, N;
int startX, startY, startDir;
int endX, endY, endDir;
int map[101][101], check[101][101][5];
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

void Input()
{
	cin >> M >> N;
	for (int i = 1; i <= M; ++i)
		for (int j = 1; j <= N; ++j)
			cin >> map[i][j];
	cin >> startY >> startX >> startDir >> endY >> endX >> endDir;
}

int Solution()
{
	int answer = 10e9;

	queue<pair<pair<int, int>, int>> q;
	q.push({ {startY, startX}, startDir });

	while (!q.empty()) {
		int ty = q.front().first.first, tx = q.front().first.second, td = q.front().second;
		q.pop();

		if (ty == endY && tx == endX && td == endDir)
		{
			answer = min(answer, check[endY][endX][endDir]);
			continue;
		}

		for (int k = 1; k <= 3; ++k)
		{
			int ny = ty + dir[td - 1][0] * k, nx = tx + dir[td - 1][1] * k;
			if (ny <= 0 || ny > M || nx <= 0 || nx > N || map[ny][nx])
				break;

			if (check[ny][nx][td] == 0 || check[ny][nx][td] > check[ty][tx][td] + 1)
			{
				check[ny][nx][td] = check[ty][tx][td] + 1;
				q.push({ {ny,nx},td });
			}
		}

		for (int nd = 1; nd <= 4; ++nd)
		{
			int rot = 1;
			if (nd == td) rot = 0;
			else if (nd == 1 && td == 2) rot = 2;
			else if (nd == 2 && td == 1) rot = 2;
			else if (nd == 3 && td == 4) rot = 2;
			else if (nd == 4 && td == 3) rot = 2;

			if (check[ty][tx][nd] == 0 || check[ty][tx][nd] > check[ty][tx][td] + rot)
			{
				check[ty][tx][nd] = check[ty][tx][td] + rot;
				q.push({ {ty,tx},nd });
			}
		}
	}

	return answer;
}

int main()
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	Input();
	cout << Solution();
}