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

www.acmicpc.net/problem/1743

1743번: 음식물 피하기

수행시간 : 25분

이 문제 풀면서 느낀게 처음보다 엄청난 발전이 있단걸 느꼇다.. 이젠 전형적인 그래프문제는 30분 이내에 해결 할 수 있는 능력이 갖춰진 것 같다. 난이도는 실버1!

이 문제의 키포인트는 범위설정! 쓰레기의 좌표가 (1,1) 부터 input 될 수 있으므로 bfs를 탐색할때 범위를 잘 생각해야된다.

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

int n, m, k;
int v_map[101][101];
bool visited[101][101];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

int bfs(int a, int b) {
	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> q;
	int cnt = 1;
	visited[a][b] = true;
	q.push({ a,b });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx > 0 && ny > 0 && nx <= n && ny <= m) {
				if (visited[nx][ny] == false && v_map[nx][ny] == 1) {
					visited[nx][ny] = true;
					cnt++;
					q.push({ nx,ny });
				}
			}
		}
	}
	return cnt;
}

void sol() {
	int mount = 0;
	int max_mount = 0;
	for (int i = 1; i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			if (v_map[i][j] == 1) {
				mount = bfs(i, j); 
				if (max_mount < mount) {
					max_mount = mount;
				}
			}
		}
	}
	cout << max_mount;
}

int main() {
	cin >> n >> m >> k;
	//v_map.resize(n, vector<int>(m));
	//visited.resize(n, vector<bool>(m));
	for (int i = 0;i < k;i++) {
		int r, c;
		cin >> r >> c;
		v_map[r][c] = 1;
	}
	sol();
}