백준 1743 - 음식물 피하기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

BFS를 이용해 푸는 문제입니다.

먼저 음식물을 배열에 저장해야합니다.

따라서 (X,Y) 좌표에 0이 아닌 다른 수를 저장해줍니다.

 

MAP을 만들었다면 음식물이 있는 곳부터 BFS를 탐색을 시작해줍니다.

탐색 시작의 조건은 음식물이 있으면서 이전에 방문하지 않았을 경우입니다.

 

탐색을 시작했다면 4방향 탐색을 통해서 음식물의 크기를 확인합니다.

탐색이 끝난 뒤, 구한 음식물의 크기를 이전의 최대 크기와 비교하면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int N, M, K;
int max_trash;
int map[101][101];
int check[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int bfs(int X, int Y) {
	queue<pair<int, int>> q;
	int Size = 1;
	q.push({ X,Y });
	check[X][Y] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				if (map[xx][yy] == 1 && check[xx][yy] == 0) {
					check[xx][yy] = 1;
					Size++;
					q.push({ xx,yy });
				}
			}
		}
	}
	return Size;
}

void solve() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (map[i][j] == 1 && check[i][j] == 0) {
				max_trash = max(bfs(i, j), max_trash);
			}
		}
	}
	cout << max_trash;
}

int main() {
	cin.tie();
	cout.tie();
	cin >> N >> M >> K;
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		map[x][y] = 1;
	}
	solve();
	return 0;
}

 

질문 및 조언은 댓글 남겨주세요