[boj][c++] 1743 음식물피하기

1743 음식물 피하기

10ra

최대 100 * 100크기의 통로에서 가장 큰 음식물을 출력하면 된다. 그래프를 탐색하면서 연결된 노드 개수만 알아내면 된다.

자료를 전부다 입력받는게 아니라 음식물 쓰레기가 있는 위치만 입력받기 때문에 좌표에 대한 이해가 필요하다. bfs로 풀기 위해 queue 컨테이너를 추가했다. n과 m이 각각 y와 x에 매칭된다는 것을 인지하는 것이 도움 됨

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

int n, m, k, ans, temp;
int graph[102][102];
bool visit[102][102];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int bfs(int y, int x)
{
	int cnt = 0;
	visit[y][x] = true;
	queue<pair<int, int>>q;
	q.push({ y,x });
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		cnt++;
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if ((nx >= 1 && nx <= m) && (ny >= 1 && ny <= n) \
            		&& visit[ny][nx] == false && graph[ny][nx] == 1)
			{
				visit[ny][nx] = true;
				q.push({ ny,nx });
			}
		}
	}
	return (cnt);
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a][b] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (graph[i][j] == 1 && visit[i][j] == false)
			{
				temp = bfs(i, j);
				ans = max(ans, temp);
			}
		}
	}
	cout << ans << endl;
}