백준 BOJ 1743 - 음식물 피하기

USACO 문제 푸는중

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

1743번: 음식물 피하기

flood-fill 문제에 해당한다

인접한 구역끼리 묶어서 가장 큰 크기의 구역을 찾는 문제.

 

플러드필 같은경우는

dfs로 구현해도 되고 bfs로 구현해도 되는데,

취향껏 구현하면 된다.

나는 bfs를 사용해서 구현해 보았다.

 

입력으로 배열이 주어지는게 아니라, 좌표값만 주어지니까

주어지는 좌표값을 이용해서 2차원 배열을 직접 만들어 주면 된다.

나는 입력으로 들어온 좌표 위치의 배열을 1로, 나머지를 0으로 채운 배열을 만들었다.

 

dx dy라는 배열을 만들어두면 탐색하기 보다 편하다.

이 문제의 경우는 인덱스가 1~N 범위라서

임의의 K에 대해서 (0,K) 나 (K,0) 좌표의 값이 모두 0으로

segmentation fault 걱정은 안해도 되는 문제이다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

int arr[123][123] = {0};
int vis[123][123] = {0};

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int bfs(int x, int y){
	queue<pair<int,int>> q;
	
	int ans = 1;
	q.push({x,y});
	vis[x][y] = 1;
	
	while(!q.empty()){
		auto pos = q.front();
		q.pop();
		
		for(int i=0; i<4; i++){
			int nx = pos.x + dx[i];
			int ny = pos.y + dy[i];
			
			if(arr[nx][ny] == 1 && vis[nx][ny] == 0){
				ans++;
				q.push({nx,ny});
				vis[nx][ny] = 1;
			}
		}
	}
	return ans;
}

int main(){
	int N,M,K;
	int x,y;
	
	cin >> N >> M >> K;
	for(int i=0; i<K; i++){
		cin >> x >> y;
		arr[x][y] = 1;
	}
	
	int ans = -1;
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			if(arr[i][j] == 1 && vis[i][j] == 0){
				ans = max(ans, bfs(i,j));
			}
		}
	}
	cout << ans;
	return 0;
}