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

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

 

문제 설명

세로(n), 가로(m), 쓰레기의 개수(k)가 주어질 때 다음 k개의 줄만큼 쓰레기의 위치가 주어진다. 쓰레기 중에서 인접한 가장 큰 쓰레기의 크기를 구하는 문제이다.

 

주요 로직

1. BFS를 사용
-> 한 음식물의 위치로부터 상하좌우를 확인해서 쓰레기의 크기를 알아낸다

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,m,k,ret,y,x;
vector<pair<int,int>> v;
int adj[103][103], visited[103][103];
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};

int bfs(int y, int x){
	int cnt = 1;
	queue<pair<int,int>> q;
	q.push({y,x});
	visited[y][x] = 1;
	while(q.size()){
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for(int i=0; i<4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny > n || nx > m) continue;
			if(visited[ny][nx] || !adj[ny][nx]) continue;
			cnt++;
			q.push({ny,nx});
			visited[ny][nx] = 1;
		}
	}
	return cnt;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> k;
	for(int i=0; i<k; i++){
		cin >> y >> x;
		v.push_back({y,x});
		adj[y][x] = 1;
	}
	
	for(int i=0; i<v.size(); i++){
		int y = v[i].first;
		int x = v[i].second;
		if(visited[y][x] || !adj[y][x]) continue;
		ret = max(ret, bfs(y,x)); 
	}
	
	cout << ret << "\n";
	
	return 0;
}