백준 1743번 (음식물 피하기, C++, DFS) / 추가 반례 [BAEKJOON]

음식물 피하기

www.acmicpc.net/problem/1743

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초128 MB122745747463047.149%

문제

코레스코 콘도미니엄 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

출처 : https://codeforces.com/blog/entry/95032


추가 반례

반례 입력 A

10 10 65
6 8
2 10
2 8
8 4
9 1
9 4
4 2
9 9
8 1
6 2
8 10
1 6
3 7
10 7
9 10
6 10
7 5
9 6
3 2
6 6
9 7
3 5
8 2
4 5
2 2
4 9
7 7
5 3
3 8
5 1
5 7
7 3
7 2
5 9
10 5
10 8
10 10
3 1
6 5
5 2
3 4
10 6
4 4
8 7
10 9
1 7
1 10
1 9
2 4
3 9
4 6
6 3
2 1
7 1
5 5
7 10
6 9
5 4
5 10
2 6
8 6
1 2
4 3
4 1
7 4

반례 출력 A

33

반례 입력 B

30 44 900
8 5
15 4
4 25
2 17
6 24
11 8
13 32
27 7
23 20
5 2
20 36
10 10
6 11
19 27
11 29
21 13
18 1
3 15
22 1
15 10
5 6
1 38
16 18
17 18
25 3
16 33
1 13
9 10
23 23
16 19
7 12
17 6
7 15
20 34
5 40
18 17
25 5
26 27
16 21
24 36
19 20
25 17
1 44
27 12
21 23
21 40
26 31
4 32
13 20
23 27
14 22
17 5
24 29
21 10
26 24
24 26
10 32
25 6
30 25
24 19
23 36
30 18
25 25
8 41
6 37
4 34
27 29
18 39
27 30
1 4
13 42
27 8
14 25
4 18
30 14
5 20
15 25
18 18
16 12
3 44
4 4
23 4
28 16
13 37
24 1
22 11
18 27
18 43
6 16
17 8
20 38
18 33
14 28
22 29
26 20
17 29
11 42
30 16
19 9
25 43
20 19
26 7
12 3
11 19
2 14
28 32
30 7
26 11
30 4
25 31
9 29
28 17
26 4
24 3
21 5
11 14
12 7
23 13
22 24
20 39
21 37
9 4
12 2
22 7
11 30
25 33
6 30
4 43
10 18
27 21
26 43
18 13
14 43
18 23
14 36
13 17
16 8
21 16
27 9
18 6
20 1
10 8
6 26
25 16
9 36
20 15
7 14
30 26
25 37
9 20
28 30
15 33
2 30
13 8
16 4
27 26
14 33
28 20
14 16
21 24
12 12
23 31
27 32
14 20
19 19
29 22
26 25
23 24
6 21
28 1
26 2
21 29
4 27
8 19
8 11
23 14
28 9
28 26
28 8
29 32
14 27
13 9
18 30
11 18
12 22
17 30
25 19
29 30
24 16
7 23
5 28
18 22
4 35
19 5
1 25
5 25
27 39
16 15
1 8
6 4
25 34
30 2
17 9
20 13
2 27
24 22
25 12
6 19
29 39
11 21
28 10
7 2
20 32
17 19
23 9
28 31
22 16
25 40
21 19
29 23
5 30
14 30
18 7
28 5
10 19
19 29
26 14
6 41
24 20
15 23
16 41
17 15
1 24
15 9
15 19
15 24
28 12
4 29
12 21
18 25
7 44
23 32
16 22
25 13
17 21
14 17
28 23
14 21
26 18
8 31
22 33
21 11
24 13
8 9
9 41
13 13
21 6
22 38
19 40
18 20
20 28
5 27
11 31
26 26
15 17
28 3
24 12
6 33
21 15
5 13
11 7
23 11
23 15
15 44
30 30
22 9
25 22
19 16
23 17
1 42
12 13
16 17
13 44
3 13
29 31
21 20
9 13
30 41
18 11
30 5
25 15
25 29
17 32
12 23
26 32
16 40
16 20
24 24
15 20
20 42
19 25
11 13
13 5
28 34
20 21
27 18
15 39
24 34
1 3
21 32
7 41
12 4
9 31
15 18
24 11
20 31
27 15
23 38
28 25
16 6
16 23
2 43
6 1
22 8
18 41
12 20
1 19
22 25
16 29
24 8
6 32
6 39
27 1
30 20
17 13
14 34
21 9
19 13
13 26
18 10
20 22
27 3
23 41
11 27
24 23
14 1
18 29
2 7
29 11
6 27
15 14
22 21
16 34
26 6
22 2
22 30
2 26
20 33
17 16
10 43
28 27
25 26
24 14
25 2
7 37
27 14
24 6
22 42
27 6
24 17
15 7
28 24
21 14
29 27
23 16
13 12
16 42
22 31
16 32
23 22
29 29
3 11
16 43
30 38
16 16
26 13
5 18
8 21
20 23
2 15
17 33
18 31
17 11
27 22
24 4
28 39
3 22
18 35
28 19
19 31
21 8
30 32
11 3
20 11
30 28
30 34
26 3
28 37
5 11
23 5
20 20
30 9
10 21
10 20
26 41
5 36
24 18
15 37
14 14
8 2
24 5
13 33
29 21
3 14
18 24
23 42
18 38
17 23
28 29
4 17
13 25
6 25
25 10
18 36
28 14
27 40
5 9
25 27
29 43
19 10
22 35
27 28
13 14
3 1
29 28
15 27
10 17
9 7
28 15
29 26
15 13
30 10
19 30
26 17
30 13
24 43
12 17
7 20
15 31
1 10
19 7
22 15
6 42
10 44
7 18
8 39
29 3
3 24
19 12
13 6
18 21
20 14
12 19
18 12
2 39
25 1
26 30
1 15
12 18
3 35
14 29
20 44
16 10
3 27
3 41
21 35
16 13
12 10
24 27
13 15
13 23
22 40
24 25
20 8
7 42
10 16
12 15
26 8
16 14
7 30
16 44
17 3
1 30
5 8
30 21
16 9
30 31
21 7
23 34
8 26
25 18
26 42
21 22
17 10
22 36
24 10
28 41
2 1
13 21
16 5
25 42
26 23
20 25
29 1
14 8
21 12
12 11
24 9
7 24
25 41
25 21
20 6
5 15
10 27
28 22
16 7
29 6
22 13
27 13
17 12
19 22
23 18
25 23
15 28
21 27
29 42
28 21
23 1
7 35
24 40
11 36
18 16
12 31
23 12
2 44
14 19
15 21
16 25
14 39
26 10
6 13
21 39
25 35
11 41
14 40
29 7
8 37
22 18
30 37
30 1
7 40
22 17
9 2
27 10
26 12
29 18
9 6
20 24
17 42
13 38
9 37
15 34
25 14
18 9
14 18
11 40
16 11
29 44
13 19
6 35
27 17
26 35
26 44
7 39
29 2
14 7
10 37
9 35
29 35
18 4
25 24
16 30
26 19
2 34
1 18
18 32
26 16
10 6
20 7
8 3
17 22
8 35
20 5
22 5
23 28
7 29
1 37
14 31
25 39
29 20
26 5
18 26
2 19
8 17
19 11
15 43
12 37
21 21
15 16
19 35
4 13
19 17
24 15
23 30
10 25
9 22
20 35
11 33
13 16
22 6
27 11
13 28
10 30
23 25
19 21
11 16
1 20
20 29
1 11
27 4
30 22
14 26
28 4
16 3
28 13
29 17
17 4
18 34
18 8
26 28
8 22
19 15
13 2
29 15
30 23
26 29
29 41
30 24
28 28
3 16
5 43
2 10
22 14
8 36
8 6
22 22
11 34
9 27
28 7
22 27
25 32
1 12
22 34
19 14
21 18
22 23
26 33
16 24
25 30
19 33
13 18
19 28
6 2
3 26
28 43
28 18
1 41
12 41
7 16
7 17
18 5
14 15
25 4
22 28
2 41
20 18
28 11
29 33
21 25
10 38
15 8
27 42
14 9
23 3
11 17
23 35
13 24
21 34
17 28
22 19
7 8
11 22
6 8
19 26
8 32
3 36
27 19
28 2
20 3
27 25
30 15
16 1
21 1
27 20
20 26
27 16
1 33
6 28
8 30
21 26
23 29
9 28
6 31
17 24
4 6
3 31
29 16
30 6
27 5
23 21
28 35
17 7
16 26
8 24
20 17
29 9
9 16
5 22
8 25
26 9
2 25
17 26
19 43
21 31
29 34
24 33
20 16
18 28
11 26
17 27
19 24
29 10
8 4
29 13
5 7
22 32
19 34
27 23
30 11
12 43
23 19
24 21
12 34
20 30
26 21
21 33
7 7
25 11
25 8
30 3
22 12
20 9
30 35
30 12
22 10
8 27
9 43
24 30
12 14
14 3
19 8
18 19
27 27
11 5
29 14
4 16
18 14
24 44
4 20
19 23
29 25
19 6
5 5
28 36
25 9
29 19
15 5
29 12
20 10
21 17
21 4
21 30
15 15
30 39
30 19
21 3
23 10
19 32
30 33
28 6
24 2
20 12
21 38
29 4
27 24
29 5
15 22
24 28
11 38
21 43
1 36
17 17
30 27
17 14
16 28
4 30
4 15
4 5
14 23
17 20
22 4
27 2
15 36
9 14
19 18
8 18
21 28
1 39
25 20
22 20
23 7
25 28
29 8
30 8
10 1
23 33
29 24
6 18
27 31
5 19
17 34
19 42
28 33
22 26
23 6
24 7
18 15
23 8
5 3
23 26
20 27
3 42
11 32
2 8
11 43
9 1
30 17
15 3
30 43
26 15
19 36
7 27
17 25
11 35
26 22
16 27
12 16
8 7
1 14
9 40

출력 B

600

음식물을 찾고 찾은 곳에서 DFS를 사용하여 연결된 음식물의 크기를 카운트 한다.

통과된 코드 (재귀)

#include<iostream>

using namespace std;

#define MAX 101

int N, M, K, cnt , result; // 가로,세로,쓰레기의 개수 // 최대 개수

int D[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
               //  상       하      좌       우

char map[MAX][MAX];
bool isVisited[MAX][MAX];

// 초기화
void Init()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			map[i][j] = '.';
			isVisited[i][j] = false;
		}
	}

	//음식물의 개수 만큼 입력을 받음
	for (; K >= 1; K--)
	{
		int x, y;
		cin >> x >> y;
		map[x][y] ='#';
		// 음식물이 있는 곳 #
	}
}

void DFS(int x, int y)
{
	cnt++;
	isVisited[x][y] = true;
	
	for (int i = 0; i < 4; i++)
	{
		// 상하 좌우로 검색
		int nx = x + D[i][0];
		int ny = y + D[i][1];

		// 범위를 벗어낫을 경우에 넘김
		if (nx <= 0 || nx > N || ny <= 0 || ny > M)
		{
			continue;
		}

		// 음식물이 있고 방문한적이 없으면 그곳에서 DFS 검색(재귀)
		if (isVisited[nx][ny]== false && map[nx][ny] == '#')
		{
			DFS(nx, ny);
		}
	}
}


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

	// 초기화
	Init();

	/* 확인용 코드
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cout << map[i][j] << ' ';
		}

		cout << "\n";
	}
	*/


	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			// 음식물이 있고 방문한 적이 없을 경우 실행
			if (map[i][j] == '#' && isVisited[i][j] == false)
			{
				cnt = 0;
				DFS(i, j);
				if (result < cnt)
				{
					result = cnt;
				}
			}
		}
	}

	cout << result;

	return 0;
}

통과된 코드 (Stack)

#include<iostream>
#include<stack>

using namespace std;

#define MAX 101

int N, M, K, cnt , result; // 가로,세로,쓰레기의 개수 // 최대 개수

// 좌표를 표현
struct Point {

	int x, y;

};


int D[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
               //  상       하      좌       우

char map[MAX][MAX];
bool isVisited[MAX][MAX];

// 초기화
void Init()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			map[i][j] = '.';
			isVisited[i][j] = false;
		}
	}

	//음식물의 개수 만큼 입력을 받음
	for (; K >= 1; K--)
	{
		int x, y;
		cin >> x >> y;
		map[x][y] ='#';
		// 음식물이 있는 곳 #
	}
}

void DFS(int x, int y)
{
	stack<Point> mystack;
	mystack.push({ x, y });


	while(!mystack.empty())
	{

		Point curr = mystack.top();
		mystack.pop();


		// 방문 했다면 넘김
		if (isVisited[curr.x][curr.y])
		{
			continue;
		}

		// 방문 마킹
		isVisited[curr.x][curr.y] = true;
		cnt++;

		for (int i = 0; i < 4; i++)
		{
			// 상하 좌우로 검색
			int nx = curr.x + D[i][0];
			int ny = curr.y + D[i][1];

			// 범위를 넘어간 경우에 넘김
			if (nx <= 0 || nx > N || ny <= 0 || ny > M)
			{
				continue;
			}

			if (isVisited[nx][ny])
			{
				continue;
			}

			if (map[nx][ny] == '.')
			{
				continue;
			}

			
			mystack.push({ nx, ny });
			
		}
	}
}


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

	// 초기화
	Init();

	/*
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			std::cout << map[i][j] << ' ';
		}

		std::cout << "\n";
	}
	*/
	

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			// 음식물이 있고 방문한 적이 없을 경우 실행
			if (map[i][j] == '#' && isVisited[i][j] == false)
			{
				cnt = 0;
				DFS(i, j);
				if (result < cnt)
				{
					result = cnt;
				}
			}
		}
	}

	std::cout << result;

	return 0;
}

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

위로 스크롤