BFS 톺아보기_섬의 개수, 음식물 피하기

youtu.be/Q6pa2akgUGI

[섬의 개수 정답 코드]

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

int field[51][51];
int visited[51][51];
//팔방 check
int dx[] = { 0,0,-1,1,-1,1,-1,1};
int dy[] = { -1,1,0,0,-1,1,1,-1 };
int n, m;
queue<pair <int, int> > q;

void bfs(int x, int y,int cnt);
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);


	while (1)
	{
		int cnt = 1;

		cin >> n >> m;
		if (n == 0 && m == 0) return 0;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> field[i][j];
				visited[i][j] = 0;
			}
		}
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (field[i][j] == 1 && visited[i][j] == 0)
				{
					bfs(i, j, cnt++);
				}
			}
		}
		cout << cnt-1<<'\n';
	}
}

void bfs(int x, int y, int cnt)
{
	q.push(make_pair(x, y));
	visited[x][y] = cnt;
	while (!q.empty())
	{
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int k = 0; k < 8; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (0 <= nx && nx < m && 0 <= ny && ny < n)
			{
				if (field[nx][ny] == 1 && visited[nx][ny] == 0)
				{
					q.push(make_pair(nx, ny));
					visited[nx][ny] = cnt;
				}
			}
		}
	}
	
}

[음식물 피하기 정답 코드]

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

int field[105][105] = { 0, };
int visited[105][105] = { 0, };
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int n, m, k, max_size = -10;

void bfs(int i, int j);
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int row, col;

	cin >> n >> m >> k;

	for (int i = 0; i < k; i++)
	{
		cin >> row >> col;
		field[row][col] = 1;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (field[i][j] == 1 && visited[i][j] == 0)
			{
				bfs(i, j);
			}
		}
	}
	cout << max_size;
	return 0;
}

void bfs(int i, int j)
{
	queue<pair<int, int> > q;
	int cnt = 0;

	q.push({ i, j });
	visited[i][j] = 1;

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

		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (1 <= nx && nx <= n && 1 <= ny && ny <= m)
			{
				if (field[nx][ny] == 1 && visited[nx][ny] == 0)
				{
					q.push({ nx, ny });
					visited[nx][ny] = 1;
				}
			}

 		}
	}
	max_size = max(max_size, cnt);
}