[BaekJoon] 백준 1926번 그림

 

[Baekjoon] 백준 1926번 그림

 

 

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

 

 

내코드

 

- BFS를 이용하는 문제

- 코드짜고 바로 통과할만큼 간단한 문제였다.

- 아래 파일은 아이패드 노타빌리티에 정리한 내용

 

백준 1926번 그림.pdf

1.87MB

 

 

#include <iostream>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int n, m;
int** arr;
bool** visited;
int num = 0, maxNum = 0;
queue<pair<int, int>> qu;

void isNear(int p, int q) {
	if (p < 0 || q < 0 || p >= n || q >= m) return;
	if (arr[p][q] == 1 && visited[p][q] == false) {
		qu.push(make_pair(p, q));
		visited[p][q] = true;
	}
}

void findArea() {
	int area = 0;
	while (!qu.empty()) {
		pair<int, int> cur = qu.front();
		qu.pop();
		area++;
		int p = cur.first;
		int q = cur.second;

		isNear(p, q - 1);
		isNear(p - 1, q);
		isNear(p, q + 1);
		isNear(p + 1, q);
	}
	if (maxNum < area) {
		maxNum = area;
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	arr = new int*[n];
	for (int i = 0; i < n; i++) {
		arr[i] = new int[m];
	}
	visited = new bool*[n];
	for (int i = 0; i < n; i++) {
		visited[i] = new bool[m];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			visited[i][j] = false;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 1 && visited[i][j] == false) {
				qu.push(make_pair(i, j));
				visited[i][j] = true;
				num++;
				findArea();
			}
		}
	}

	cout << num << "\n" << maxNum;

	return 0;
}

 

참고