백준 1473 - 음식물 피하기

문제

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

 

풀이

상하좌우로 탐색하며 음식물이 있는지 없는지 검사하여 최대값을 찾으면 된다. 

 

1. 2차원 배열을 돌면서 음식물이 있는 곳(1)을 찾는다.

2. 음식물이 있는 곳은 0으로 바꾼다

3.. 음식물이 있는 곳에서 상하좌우를 재귀적으로 검사한다.

4. 2차원 배열을 다 돌 때까지 2, 3을 반복한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int graph[102][102];
 
int N, M, K;
int result;
 
void getmax(int row, int col)
{
    result++;
    graph[row][col] = 0;
 
    if (graph[row - 1][col])
    {
        graph[row - 1][col] = 0;
        getmax(row - 1, col);
    }
 
    if (graph[row + 1][col])
    {
        graph[row + 1][col] = 0;
        getmax(row + 1, col);
    }
 
    if (graph[row][col - 1])
    {
        graph[row][col - 1] = 0;
        getmax(row, col - 1);
    }
 
    if (graph[row][col + 1])
    {
        graph[row][col + 1] = 0;
        getmax(row, col + 1);
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N >> M >> K;
 
    int r, c;
    for (int i = 0; i < K; i++)
    {
        cin >> r >> c;
 
        graph[r][c] = 1;
    }
 
    vector<int> v;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (graph[i][j])
            {
                result = 0;
                getmax(i, j);
                v.push_back(result);
            }
        }
    }
    sort(v.begin(), v.end(), greater<int>());
 
    cout << v[0];
 
    return 0;
}