음식물 피하기
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 12274 | 5747 | 4630 | 47.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번
출처 : 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; }
![](https://blog.kakaocdn.net/dn/yYFRJ/btrJHdONZtJ/BzMDur2krKCy2K5Q9HL6e0/img.png)
통과된 코드 (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; }
![](https://lycos7560.com/wp-content/uploads/image-45.png)