BOJ_1926_그림

이 글은 공부하는 "학생"의 글로, 명확하지 않은 정보가 있을 수 있습니다. 따라서 보시는 분이 계실 경우, '참고'만 해주시면 감사드리겠습니다. 오류가 발견될 시, 댓글 달아주시면 정말 감사드리겠습니다.

BFS 문제는 코테에서 정말 많이 나온다.
살짝 꼬아서 자주 등장하는 것 같은데, 그럴 때마다 못알아 채는 경우도 있다.
그래서 왜 BFS로 풀이를 한 것인지, 접근 법부터 공부를 해보고자 한다.

문제 출처 : https://www.acmicpc.net/problem/1926

접근 방법

• 우선 도화지가 주어진다(n(1~500), m(1~500))
  -> 이 점에서 우선 좌표를 활용한 문제임을 확인할 수 있다.
• 그림의 넓이, 그림의 갯수를 물어보는 문제이다.
  -> "넓이"의 단어부터 너비우선 탐색 문제임을 확인할 수 있다.
• 500 * 500 = 250000(25만)
  -> O(NlogN)까지는 가능한 문제이다.
  -> 하지만 BFS는 기본적으로 O(N)이므로 시간 복잡도도 충분해 보인다.

시간 복잡도 : O(N * M)

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

int n, m, p_count;
int arr[502][502];
int vis[502][502];
int psize = 0;	// psize의 최대값을 구해야 한다. 없는 경우 0
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };


void BFS(pair<int, int> start) {
	int temp = 1;
	queue<pair<int, int>> Q;
	Q.push(start);
	vis[start.first][start.second] = 1;
	while (!Q.empty()) {
		auto curr = Q.front(); Q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curr.first + dx[i];
			int ny = curr.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (vis[nx][ny] != 0 || arr[nx][ny] == 0)continue;
			vis[nx][ny] = 1;
			temp++;
			Q.push({ nx, ny });
		}
	}
	psize = max(psize, temp);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 1 && vis[i][j] == 0) {
				p_count++;
				BFS({ i, j });
			}
		}
	}
	cout << p_count << "\n" << psize;
	return 0;
}