BOJ - 1743. 음식물 피하기

문제

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

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

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

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

입력

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

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.

출력

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

예제 입력 1

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

예제 출력 1

4

---

풀이 과정

• 인접배열과 BFS를 사용한 완전 탐색으로 구현하였습니다.
• 입력받은 정점과 간선을 배열로 바꿔 저장한 이후 상하좌우로 탐색을 진행하였습니다.
• 무게는 이전에 방문한 좌표를 누적해가며 합하여 구하고 리턴하여 구했습니다.
• 전체 좌표를 시작점으로 다 한번씩 완전 탐색하며 어떤 값이 가장 큰지 구해주면 됩니다.

---

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;
int n,m,k;
bool check[101][101];
int arr[101][101];
queue<pair<int,int>> q;
int nx[] = {1,-1,0,0};
int ny[] = {0,0,1,-1};

int bfs(int y,int x){
    q.push(make_pair(y,x));
    check[y][x]=true;
    int trashWeight = arr[y][x];
    //cout<<"Trashweight"<<trashWeight<<" ";

    while(!q.empty()){
        int curY = q.front().first;
        int curX = q.front().second;
        q.pop();

        for(int i=0;i<4;i++){
            int newY = curY + ny[i];
            int newX = curX + nx[i];

            if(newX<1 || newY<1 ||newX>m || newY>n){
                continue;
            }
            if(check[newY][newX]==false && arr[newY][newX]>=1){
                q.push(make_pair(newY,newX));
                check[newY][newX]=true;
                trashWeight=trashWeight+arr[newY][newX];
                //cout<<trashWeight;
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            check[i][j]=false;
        }
    }

    return trashWeight;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){
        int r,c;
        cin>>r>>c;
        arr[r][c]++;
    }
    int max = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(max<bfs(i,j) && arr[i][j]>=1){
                //cout<<"i: "<<i<<" j: "<<j<<"  "<<bfs(i,j)<<'\n';
                max = bfs(i,j);
            }
        }
    }

    cout<<max;




    return 0;
}