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

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

1743번: 음식물 피하기

 

이차원 배열 map을 만들고 음식물 위치에 모두 1을 대입해준다. 모든 경로를 탐색하면서 아직 방문하지 않았고, map의 값이 1이면 bfs를 통해 연속된 1을 찾아주면 된다. 이때 bfs는 연속된 1의 개수를 반환해주는데, 마지막에 최대값을 출력해주기만 하면 된다. 

 

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

int N, M, K;
int map[101][101];
int visit[101][101];

int check(int row, int col){
    int move[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    
    queue<pair<int, int>> q;
    q.push({row, col});
    visit[row][col] = 1;
    
    int n_row, n_col;
    int cnt = 1;
    
    while(!q.empty()){
        row = q.front().first;
        col = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            n_row = row + move[i][0];
            n_col = col + move[i][1];
            if(n_row >= 1 && n_col >= 1 && n_row <= 100 && n_col <= 100){
                if(!visit[n_row][n_col] && map[n_row][n_col] == 1){
                    visit[n_row][n_col] = 1;
                    cnt++;
                    q.push({n_row, n_col});
                }
            }
        }
    }
    
    return cnt;
}

int main(){
    cin >> N >> M >> K;
    int r, c;
    
    for(int i = 0; i < K; i++){
        cin >> r >> c;
        map[r][c] = 1;
    }
    
    int ans = 0;
    
    //연속된 1의 최대 개수를 구하면 된다.
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(!visit[i][j] && map[i][j] == 1)
                ans = max(ans, check(i, j));
        }
    }
    
    
    cout << ans << endl;
    
    return 0;
}