[BOJ / C++] 1743: 음식물 피하기

링크

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

1743번: 음식물 피하기

 

풀이 과정

2차원 배열을 BFS로 탐색하는 방식으로 풀었다.

2차원 배열이기 때문에 pair<int, int>를 사용했고, food 변수에 해당 BFS 탐색에서의 음식물의 크기를 저장했다.

그리고 강의에서 배웠던 방식대로 dx[], dy[]를 이용해서 2차원 배열을 탐색했다.

 

이 외에는 딱히 기본적인 BFS와 크게 다른 점이 없어서 전체적인 틀 짜는 것 자체는 어렵지 않은 문제였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

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

int map[101][101] = { 0, };
int visited[101][101] = { 0, };
queue<pair<int, int>> q;

int N, M, K;
int food = 1;

void bfs(int x, int y) {
	visited[x][y] = 1;
	q.push(make_pair(x, y));

	while (!q.empty()) {
		x = q.front().first;
		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 || nx > N || ny < 0 || ny > M) continue;
			if (map[nx][ny] == 1 && visited[nx][ny] == 0) {
				visited[nx][ny] = 1;
				q.push(make_pair(nx, ny));
				food++;
			}
		}
	}
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int ans = 0;

	cin >> N >> M >> K;
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;

		map[x][y] = 1;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (visited[i][j] == 0 && map[i][j] == 1) {
				bfs(i, j);
				ans = max(ans, food);
				food = 1;
			}
		}
	}

	cout << ans;

	return 0;
}