백준 1743 음식물 피하기 [DFS]

알고리즘/BOJ

백준 1743 음식물 피하기 [DFS]

꾸준한나 2020. 4. 6. 02:23

문제 링크 : https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아

www.acmicpc.net

문제 풀이

DFS 알고리즘을 이용해서, 가장 큰 음식물의 크기를 구해주면 됩니다.

기존에 구한 음식물의 크기보다 더 큰 음식물의 크기를 구했다면, 갱신시키면서 답을 찾아가면 됩니다.

소스 코드

#include <iostream>
#include <vector>

#define MAX_SIZE 100 + 1
using namespace std;

vector<pair<int, int>> pos;
int a[MAX_SIZE][MAX_SIZE];
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int N, M, K, ans, cnt;

void dfs(int x, int y)
{
	cnt++;
	a[x][y] = 0;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && nx < N && ny < M)
		{
			if (a[nx][ny] == 1) dfs(nx, ny);
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> N >> M >> K;
	for (int i = 0; i < K; i++)
	{
		int r, c;
		cin >> r >> c;
		a[r - 1][c - 1] = 1;
		pos.push_back({ r - 1,c - 1 });
	}

	for (int i = 0; i < pos.size(); i++)
	{
		cnt = 0;

		int x = pos[i].first;
		int y = pos[i].second;

		if (a[x][y] == 1) dfs(x, y);
		if (cnt > ans) ans = cnt;
	}

	cout << ans << '\n';
	return 0;
}