20250318

방문한 정점 → 다시 방문하지 않는다. ⇒ Visited

연결된 컴포넌트(Connected Component)

연결된 하위그래프를 말하며 연결된 하나의 덩어리를 생각하자.

이 덩어리는 연결된 컴포넌트에 속한 “모든 정점을 연결하는 경로가 있다.”라는 특징이 있다.

깊이 우선 탐색(DFS, Depth First Search)

DFS는 그래프를 탐색할 때 쓰는 알고리즘이며 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리(깊이) 있는 노드까지 탐색하는 알고리즘.

#include <bits.stdc++.h>
using namespace std;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int m, n, k, y, x, ret, ny, nx, t;
int a[104][104];
bool visited[104][104];
void dfs(int y, int x)
{
	visited[y][x] = 1;
	for(int i = 0; i < 4; i++)
	{
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue; // 오버플로우, 언더플로우 방지 
		if (a[ny][nx] == 1 && !visited[ny][nx]) // 방문 가능한곳이면서 방문했던 적이 없는곳이면 DFS 진행 
		{
			dfs(ny, nx);	
		}	
	} 	
} 
int main() 
{
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 1 && !visited[i][j])
			{
				ret++; 
				dfs(i, j);
			}
		}
	}
	cout << ret << '\n';
	return 0;
}