[백준 1743번] 음식물 피하기

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

1743번: 음식물 피하기

<문제 풀이> BFS 알고리즘

 

먼저 2차원 배열을 선언하고, 음식물이 있는 곳을 1로 표현하고 음식물이 없는 곳을 0으로 표현합니다.

 

그다음 (r,c)에 있는 음식물에 대해서 인접한 음식물의 크기를 구할 수 있는 BFS를 구현합니다.

크기를 구하는 방법은 기본적인 BFS 구현에서 큐에 탐색할 next 좌표를 넣을 때 크기를 1 증가시키는 코드만 추가하면 됩니다.

 

구현한 BFS를 모든 음식물 각각에 대해서 호출하면 되는데, 이전에 BFS로 방문했던 곳에 대해서는 BFS를 호출하지 않도록 해야 합니다.

 

 

 

<C++소스코드>

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
#define X first
#define Y second
 
int n, m, k;
 
bool board[101][101];
bool visited[101][101];
const int dx[4] = { 0,0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
 
int bfs(int x, int y) {
    int size = 1;
    queue<pair<int, int> > Q;
    Q.push({ x, y });
    visited[x][y] = true;
 
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 1 || ny <1 || nx > n || ny > m) continue;
            if (!board[nx][ny] || visited[nx][ny]) continue;
            Q.push({ nx, ny });
            visited[nx][ny] = true;
            size++;
        }
    }
    return size;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> m >> k;
    while (k--) {
        int r, c; cin >> r >> c;
        board[r][c] = true;
    }
 
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!board[i][j] || visited[i][j]) continue;
            ans = max(ans, bfs(i, j));
        }
    }
    cout << ans;
    return 0;
 
}