방구 문제

강의 들으면서 그래프와 DFS 정리하면서 푼 문제이다.

방구문제

뭐 문제는 말도 안되는 방구로 맵을 정복을 한다는 어쩌구인데 결국 DFS와 비슷한 문제임.

다만 2차원 배열을 사용해야한다는 점과

Connected Component를 알아야한다는 점이다.

근데 Connected Component라는 개념이 엄청 중요한 개념은 아님. 그냥 그래프 집합이 몇개인지를 말하는 부분임.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define endl "\n"

vector<vector<int>> vec;
vector<vector<bool>> visited;
int n, m, cnt = 0;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};

void CM()
{
	cin >> n >> m;

	vec.resize(n);
	visited.resize(n);

	for (int i = 0; i < n; ++i)
	{
		vec[i].resize(m);
		visited[i].resize(m);
	}

	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < m; ++j) cin >> vec[i][j];
}

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= m) return false;
	return true;
}

void go(int y, int x)
{
	visited[y][x] = true;
	cout << y << ", " << x << endl;

	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (Cango(ny, nx) == false) continue;
		if (visited[ny][nx] == true) continue;
		if (vec[ny][nx] == 0) continue;

		go(ny, nx);
	}
}

void goAll()
{
	for (int y = 0; y < vec.size(); ++y)
	{
		for (int x = 0; x < vec[y].size(); ++x)
		{
			if (vec[y][x] == 0) continue;
			if (visited[y][x] == true) continue;
			go(y ,x);
			++cnt;
		}
	}
}

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

	CM();
	goAll();

	cout << cnt << endl;

	return 0;
}

다만 주의해야할 부분이 Cango에서 >= 이거 범위 체크하는 부분 주의 해야한다,

인덱스는 같을 수 없다.