백준 1743: 음식물 피하기

문제 요약

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.

선생님을 도와 제일 큰 음식물의 크기를 구하자.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS

문제 풀이

이번 탐색에서는 구성 요소의 개수를 세기 위해 DFS()가 호출될 때마다 카운트를 증가시키면 된다.

첫 호출시에만 카운트를 0으로 초기화하고, 이후에 호출된 함수의 횟수만 카운트하고, 이 카운트한 값의 최대값을 구하면 된다.

인덱스가 0이 아닌 1로 시작하는 것에 주의하자.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

bool visited[100][100];
int map[100][100];
int cnt, m, n;

void dfs(int i, int j) {
	cnt++;
	visited[i][j] = true;
	if (i < n - 1)
		if (map[i + 1][j] && !visited[i + 1][j]) dfs(i + 1, j);
	if (i > 0)
		if (map[i - 1][j] && !visited[i - 1][j]) dfs(i - 1, j);
	if (j < m - 1)
		if (map[i][j + 1] && !visited[i][j + 1]) dfs(i, j + 1);
	if (j > 0)
		if (map[i][j - 1] && !visited[i][j - 1]) dfs(i, j - 1);
}
int main()
{
	int k, in1, in2, max = 0;
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		scanf("%d%d", &in1, &in2);
		map[in1 - 1][in2 - 1] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j]) {
				if (map[i][j]) {
					cnt = 0;
					dfs(i, j);
					if (cnt > max) max = cnt;
				}
				else visited[i][j] = true;
			}
		}
	}
	cout << max;
	return 0;
}