취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1743번 문제인 음식물 피하기이다.
문제는 아래 링크를 확인하자.

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

주어진 2차원배열에서 가장 크게 뭉친 쓰레기 덩어리를 찾는 문제이다.

BFS 등의 알고리즘을 이용하여 가장 큰 connected component의 크기를 구해주자.

아래의 dr, dc 배열 등을 이용하면 조금 더 구현을 편하게 할 수 있다.

또한 셌던 덩어리를 또다시 셀 필요는 없으므로 visited 배열을 관리하여 중복된 탐색을 건너뛰자.

아래는 제출한 소스코드이다.

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

bool visited[100][100];
bool board[100][100];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

int main() {
	int R, C, N; cin >> R >> C >> N;
	while (N--) {
		int r, c; cin >> r >> c; r--; c--;
		board[r][c] = 1;
	}

	int ans = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (visited[r][c] || board[r][c] == 0) continue;
			queue<pair<int, int>> que;
			que.push(make_pair(r, c));
			int cnt = 0;
			visited[r][c] = 1;
			while (!que.empty()) {
				cnt++;
				int x = que.front().first, y = que.front().second; que.pop();
				for (int k = 0; k < 4; k++) {
					int rr = x + dr[k], cc = y + dc[k];
					if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
					if (board[rr][cc] && visited[rr][cc] == 0) {
						visited[rr][cc] = 1;
						que.push(make_pair(rr, cc));
					}
				}
			}
			ans = max(ans, cnt);
		}
	}

	cout << ans;
}