[백준] 1743 음식물 피하기 C++

 

[실버 1] 1743 음식물 피하기

1743번: 음식물 피하기

[알고리즘 분류]

그래프 이론

그래프 탐색

너비 우선 탐색

깊이 우선 탐색

 

2 초

128 MB

15782

7371

5838

46.775%

문제

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

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

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

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라. 

예제 입력 1

3 4 5
3 2
2 2
3 1
2 3
1 1

예제 출력 1

4

힌트

# . . .
. # # .
# # . .

위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

 

[접근법]

r X c 배열에 음식물 쓰레기 좌표를 1로 지정하고, 나머지 공간을 0으로 설정하면 영역을 명확하게 나눌 수 있다.

우리가 해야할 것은 오로지 1로 적힌 부분만 BFS를 적용하여 연결된 크기를 측정하면 된다.

 

#include <iostream>
#include <queue>

using namespace std;

int board[101][101];
bool visited[101][101];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

// 가장 큰 음식물 크기 찾아내기
// 음식물을 발견할 때마다 bfs로 주위 음식물을 다 찾은 다음,
// 기존 최댓값과 크기를 비교하여 갱신한다.
int	findBiggest(int n, int m)
{
	queue<pair<int, int> > Q;
	int biggest = 0;
	int count = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (board[i][j] == 1 && visited[i][j] == false)
			{
				count = 0;
				Q.push(make_pair(i, j));
				visited[i][j] = true;
				while(!Q.empty())
				{
					auto cur = Q.front();
					Q.pop();
					count++;
					for (int dir = 0; dir < 4; dir++)
					{
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						
						if (nx < 1 || nx > n || ny < 1 || ny > m)
							continue;
						if (board[nx][ny] == 0 || visited[nx][ny])
							continue;
						Q.push(make_pair(nx, ny));
						visited[nx][ny] = true;
					}
				}
				biggest = max(count, biggest);
			}
		}
	}
	return biggest;
}

int main()
{
	int n, m, k, r, c, ans;
	cin >> n >> m >> k;

	// 음식물 위치 입력받아서 지도에 저장.
	// 음식물은 1, 빈 공간은 0으로 표시
	for (int i = 0; i < k; i++)
	{
		cin >> r >> c;
		board[r][c] = 1;
	}

	// 가장 큰 음식물 찾기!
	ans = findBiggest(n, m);
	cout << ans << '\n';
	return 0;
}