백준 1743 음식물 피하기, c++

 

 

 

작성한 코드는 다음과 같다.

주어진 NxM 행렬에 대해 bfs 알고리즘으로 탐색해, 문제에서  원하는 만큼의 영역을 구해 출력하는 문제였다.

전체 코드 구조는 비슷하지만 조금씩 응용되어 문제가 나오기 때문에 코드를 완벽히 이해하고 문제에 맞게 적용할 수 있도록 더 연습해야겠다.

(백준 1303과 유사)

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

int n, m, k, max_result = 0, dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int b[101][101] = {-1,};
queue<pair<int, int>> q;
bool visited[101][101];

void bfs(int r, int c, int team) {
    q.push({ r, c });
    visited[r][c] = true;

    int cnt = 0;
    while (!q.empty()){
        pair<int, int> now = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < 4; i++) {
            int nr = now.first + dir[i][0], nc = now.second + dir[i][1];
            if (1<=nr && nr<=n && 1<=nc && nc<=m && 
                !visited[nr][nc] && b[nr][nc]==1) {
                visited[nr][nc] = true;
                q.push({ nr, nc });
            }
        }
    }
    
    if(cnt > max_result)
        max_result = cnt;
}

int main(){
    cin >> n >> m >> k;
    
    //b(nxm)를 0으로 초기화
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            b[i][j] = 0;
    
    //b에 음식물 있는 자리 1로 표시
    int a1, a2;
    for (int i=1; i<=k; i++){
        cin >> a1 >> a2;
        b[a1][a2] = 1;
    }
    
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            if (!visited[i][j] && b[i][j]==1)
                bfs(i, j, b[i][j]);

    cout << max_result;
    
    return 0;
}