음식물 피하기 (feat. 백준, 1743번)

음식물 피하기
https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
bool arr[101][101], visit[101][101];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    memset(arr, false, sizeof(arr));
    memset(visit, false, sizeof(visit));
    register int N, M, K, ans = 0, dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
    cin >> N >> M >> K;
    for(register int k = 0, n, m; k < K; ++k)
        cin >> n >> m, arr[n][m] = true;
    for(register int n = 1, m, t; n <= N; ++n)
        for(m = 1; m <= M; ++m)
            if(!visit[n][m] && arr[n][m]){
                t = 1;
                queue<pair<int, int>> q;
                q.push(make_pair(n, m));
                visit[n][m] = true;
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    register int x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny] && arr[nx][ny])
                            ++t, visit[nx][ny] = true, q.push(make_pair(nx, ny));
                    }
                }
                ans = max(ans, t);
            }
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

1. 전형적인 bfs 유형의 문제입니다.
2. 상,하,좌,우 로 연결된 쓰레기의 개수가 가장 큰 값을 찾는 문제입니다.