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

문제 링크: www.acmicpc.net/problem/1743

1743번: 음식물 피하기

1. 주의할 점

- BFS로 해결하도록 한다

 

2. 구현

- Check[][] 배열을 통해 음식물이 있는 좌표는 true로 갱신한다. 문제는 좌측 상단의 좌표가 (1,1)이므로 입력받는 좌표들에 대해 -1씩 한 좌표에 음식물을 표시한다

- 전체 Check[][] 배열에 대해 탐색을 시작하며, 음식물인 지점을 주변으로 4방향 탐색을 실시하여 음식물의 크기를 구한다

- 가장 큰 음식물의 크기를 Result에 저장한다

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct info{
    int x,y;
};
info tmp;
int row,col,num,y,x,result=0;
bool check[100][100]={false,};
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

int main() {
    cin >>row>>col>>num;
    for(int i=0;i<num;i++){
        cin>>y>>x;
        check[y-1][x-1]=true;
    }
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            if(check[i][j]){
                int cnt=1;
                queue<info> q;
                check[i][j]=false;
                tmp.x=j;
                tmp.y=i;
                q.push(tmp);
                while(!q.empty()){
                    int cx = q.front().x;
                    int cy = q.front().y;
                    q.pop();
                    for(int k=0;k<4;k++){
                        int nx = cx + dx[k];
                        int ny = cy + dy[k];
                        if(nx>=0 && ny>=0 && nx<col && ny<row && check[ny][nx]){
                            check[ny][nx]=false;
                            cnt++;
                            tmp.x=nx;
                            tmp.y=ny;
                            q.push(tmp);
                        }
                    }
                }
                result = max(result,cnt);
            }
        }
    }
    cout<<result;
    return 0;
}