알고리즘 : DFS와 BFS (3) - 기초 문제 풀이 (C++로 구현)

1. 음료수 얼려 먹기

connected component를 찾는 문제이다. 

 

얼음을 얼릴 수 있는 공감이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 다음과 같이 3 x 3 크기의 얼음틀이 있다고 가정하면 위 그림과 같이 그래프로 만들 수 있다. 상, 하, 좌, 우로 연결되어 있는 노드들은 인접한 형태가 된다. 

특정 지점에서 BFS 또는 DFS를 수행해서 이동 가능한 모든 경로에 대해서 다 방문처리를 진행하도록 처리할 수 있다. 

 

 

1) BFS를 이용해서 구현

#include<iostream>
#include <queue>
using namespace std;
bool notAllowed[1001][1001];
int n, m;
void bfs(int row, int col) {
	queue <pair<int, int> > q;
	q.push({ row, col });
	notAllowed[row][col] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		// cout << "(" << x << "," << y << ") ";
		q.pop();
		if (x - 1 > 0) {
			if (notAllowed[x - 1][y] == 0) {
				notAllowed[x - 1][y] = 1;
				q.push({ x - 1, y });
			}
		}
		if (y - 1 > 0) {
			if (notAllowed[x][y - 1] == 0) {
				notAllowed[x][y - 1] = 1;
				q.push({ x, y - 1 });
			}
		}
		if (y + 1 <= m) {
			if (notAllowed[x][y + 1] == 0) {
				notAllowed[x][y + 1] = 1;
				q.push({ x, y + 1 });
			}
		}
		if (x + 1 <= n) {
			if (notAllowed[x + 1][y] == 0) {
				notAllowed[x + 1][y] = 1;
				q.push({ x + 1, y });
			}
		}
	}
}

int main() {
	cin >> n >> m;
	vector<string> ice(n);
	for (int i = 0; i < n; i++)
	{
		cin >> ice[i];
		for (int j = 0; j < m; j++)
		{
			notAllowed[i + 1][j + 1] = ice[i][j] - '0';
		}
	}

	int count= 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <=m; j++)
		{
			if (notAllowed[i][j] != 1) {
				bfs(i, j);
				// cout << endl;
				count++;
			}
		}
	}
	cout << count;
}

 

vector로 graph를 구현하지 않아도 된다. (상, 하, 좌, 우)에 있는 노드와 모두 연결이 되어있다는 것은 모든 모드에게 해당되는 일이므로 graph.size()와 같은 값이 필요 없기 때문이다. 

음료수 얼려먹기를 BFS를 이용해서 c++로 구현한 코드가 없는 것 같아서 직접 구현해봤다.

 

 

2) DFS를 이용해서 구현

void dfs(int row, int col) {
	notAllowed[row][col] = 1;
	if (row - 1 > 0) {
		if (notAllowed[row - 1][col] == 0) {
			dfs(row - 1, col);
		}
	}
	if (col - 1 > 0) {
		if (notAllowed[row][col - 1] == 0) {
			dfs(row, col - 1);
		}
	}
	if (col + 1 <= m) {
		if (notAllowed[row][col + 1] == 0) {
			dfs(row, col + 1);
		}
	}
	if (row + 1 <= n) {
		if (notAllowed[row + 1][col] == 0) {
			dfs(row + 1, col);
		}
	}
}

main은 dfs(i, j)로 BFS의 main 코드와 동일해서 생략했다. 

 

bool dfs(int i, int j){
    if(i < 0 || i >= N || j < 0 || j >= M) return false;

    if(v[i][j] == 0){
        v[i][j] = 1;
        dfs(i-1, j);
        dfs(i+1, j);
        dfs(i, j-1);
        dfs(i, j+1);
        return true;
    }

    return false;
}

유튜브에서 제시한 dfs 함수이다.

 

 

2. 미로탈출

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일하다.

(1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.

예를 들어 3 x 3 크기의 미로가 존재한다고 가정하였다.

(1, 1)에서 탐색을 진행하면 (1, 2) 위치의 노드를 방문하게 되고, (1, 2) 노드의 값을 2로 바꾼다. (거리에 해당하는 숫자로)

 

#include<iostream>
#include<vector>
#include <queue>
using namespace std;
int safe[201][201];
int n, m;
int result;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
void bfs(int x, int y) {
	queue <pair<int, int> > q;
	q.push({ x, y });
	while (!q.empty()) {
		int row = q.front().first;
		int col = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = row + dx[i];
			int ny = col + dy[i];
			//if (nx == 1 && ny == 1)
			//	continue;
			if (nx <= 0 || nx > n || ny <= 0 || ny > m)
				continue;
			// 몬스터 있는 경우
			if (safe[nx][ny] == 0)
				continue;
			if (safe[nx][ny] == 1) {
				safe[nx][ny] = safe[row][col] + 1;
				q.push({ nx, ny });
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string map;
		cin >> map;
		for (int j = 0; j < map.length(); j++)
		{
			safe[i + 1][j + 1] = map[j] - '0';
		}
	}
	bfs(1, 1);
	cout << safe[1][1];	
}

c++로 구현한 코드이다. 거리로 저장해주는 것이 핵심이었다.