boj1926-풀이

boj.kr/1926 그림 (문제)

풀이

---

그래프 문제

queue를 사용하는 bfs를 통해 풀었다.
queue에는 다음으로 탐색할 노드위 위치(y, x)를 저장.

1. $n \times m$크기의 맵에서 순차적으로 탐색하여, 탐색할 노드(1)를 찾아서 queue에 넣는다.
   탐색할 노드를 찾으면,
   • 현재 그림의 크기를 1로 초기화
   • 그림의 수에 1을 더한다.
   • 다음에 다시 방문하지 않도록 방문처리를 한다.
     (이후 bfs 진행)
   1. queue가 비어있지 않으면 2번부터, 비어있다면 4번부터 실행
   2. queue에서 뽑아냄(pop)
   3. 뽑아낸 원소의 인접 4방향에 대해서, 다음으로 탐색할 노드를 찾는다.
      다음으로 탐색할 노드는 아직 탐색하지 않은 노드로 값이 1임. 탐색할 노드를 찾으면,
      • 다음에 다시 방문하지 않도록 방문처리를 한다.(값을 0으로 변경한다. 0=방문완료, 1=미방문)
      • 다음에 탐색하도록 queue에 넣는다.
      • 현재 그림의 크기에 1을 더한다.
   4. 현재 그림의 크기와 기존 최대 그림의 크기를 비교하여 더 큰 그림의 크기를 저장한다.
2. 그림의 수, 가장 큰 그림의 크기 출력!

구현

---

#include <bits/stdc++.h>
using namespace std;
#define Y first
#define X second
typedef pair<int, int> pii;

bool isInArea(int y, int x, int my, int mx, int My, int Mx) {
	return (my <= y && y < My) && (mx <= x && x < Mx);
}

bool isInArea(pii cur, pii picMin, pii picMax) {
	return isInArea(cur.Y, cur.X, picMin.Y, picMin.X, picMax.Y, picMax.X);
}

pii operator+(const pii& origin, const pii& sum) {
	return { origin.first + sum.first, origin.second + sum.second };
}
pii ways4[] = { // {y, x}
	{-1, 0}, //up
	{1, 0}, //down
	{0, -1},//left
	{0, 1},//right
};

pii msize;
int arr[500][500];
queue<pii> q;
int picMax = 0, picCnt;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> msize.Y >> msize.X;
	for (int i = 0; i < msize.Y; ++i)
		for (int j = 0; j < msize.X; ++j)
			cin >> arr[i][j];
	for (int i = 0; i < msize.Y; ++i){
		for (int j = 0; j < msize.X; ++j) {
			if (arr[i][j]) {
				++picCnt;
				arr[i][j] = 0;
				q.push({ i, j });
				int picSize = 1;
				// bfs
				while (!q.empty()) {
					pii cur = q.front();
					q.pop();
					for (int i = 0; i < 4; ++i) {
						pii next = cur + ways4[i];
						if (isInArea(next, { 0, 0 }, msize) && arr[next.Y][next.X]) {
							++picSize;
							arr[next.Y][next.X] = 0;
							q.push(next);
						}
					}
				}
				picMax = max(picMax, picSize);
			}
		}
	}
	cout << picCnt << '\n' << picMax;
	return 0;
}

TMI

---

전역전 휴가~ :)