[백준 BOJ1743] 음식물 피하기 (C++)

1. 제목

- 백준 1743 음식물 피하기

- BOJ 1743 음식물 피하기

문제 링크 : 1743번: 음식물 피하기 (acmicpc.net)

---

2. 문제 설명

음식물 피하기 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	11539	5382	4316	46.933%

문제

코레스코 콘도미니엄 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가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO November 2007 Contest > Bronze 3번

• 문제를 번역한 사람: author9
• 문제의 오타를 찾은 사람: eric00513
• 데이터를 추가한 사람: wbcho0504

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

---

3. 풀이 과정

탐색알고리즘만 알고 있다면 쉽게 풀 수 있는 문제였어요.
저 같은 경우는 맵 0, 0 좌표부터 탐색을 시작하여 쓰레기가 발견되면 그 지점부터 DFS 탐색을 시작해 주변 지역에 있는 쓰레기 범위를 구하여 result 변수에 저장하여 모든맵 탐색을 끝냈을 때 가장 최댓값을 구하는 방식으로 해결했어요.

---

4. 코드

#include <iostream>
#include <stack>

#define X first
#define Y second
#define MAX 100 + 2

using namespace std;

int map[MAX][MAX];
int visit[MAX][MAX];
//			상 하 좌 우
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

// N : 세로 길이, M : 가로 길이, K : 쓰레기의 개수
int N, M, K;
int result;

void Dfs(int x, int y)
{
	int cnt = 1;
	stack<pair<int, int>> s;
	s.push({x, y});
	visit[x][y] = 1;

	while (!s.empty())
	{
		pair<int, int> cur = s.top();
		s.pop();

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 1 || ny < 1 || nx > M || ny > N)
				continue;

			if (visit[nx][ny] == 1 || map[nx][ny] == 0)
				continue;

			s.push({nx, ny});
			visit[nx][ny] = 1;
			cnt++;
		}
	}
	if (result < cnt)
		result = cnt;
}

int main()
{
	cin >> N >> M >> K;

	// 맵 정보 입력
	// 쓰레기가 있는곳 좌표만 1로 설정
	for (int i = 0; i < K; i++)
	{
		int x, y;
		// 입력을 y , x로 줌
		cin >> y >> x;
		map[x][y] = 1;
	}

	for (int y = 1; y <= N; y++)
	{
		for (int x = 1; x <= M; x++)
		{
 			if (visit[x][y] == 0 && map[x][y] == 1)
			{
				Dfs(x, y);
			}
		}
	}

	cout << result;
	return 0;
}