백준 16932 모양 만들기 c++ (bfs,dfs)

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

16932번: 모양 만들기

문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 0과 1의 개수는 하나 이상이다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 브루트포스 알고리즘
• 너비 우선 탐색
• 깊이 우선 탐색

풀이

해당 문제를 보고, 그래프의 0인 곳들을 모두 bfs 혹은 dfs로 탐색하여 1로 만들어진 모양의 최대 개수를 찾는 풀이를

쉽게 생각할 수 있을 것이다.

이 풀이대로 풀면, 0인 좌표를 탐색할 때마다 visited배열을 초기화해줘야 하는데, 최소 N * N * N으로 O(N^3)의 시간 복잡도를 갖는데 N은 1000이기 때문에 주어진 2초이 시간을 초과한다.

 

본인은 시간 복잡도를 줄이기 위한 방법으로 모든 0을 탐색하되, 1인 모양들을 그룹화하고, 그룹별로 모양들의 크기를 저장해서, 0의 dfs 혹은 bfs로 탐색하는 해야 하는 가지수를 줄였다.

위의 첫 번째 입력의 예시를 살펴보자.

	1,3	1,3
	0	1,3
	2,1

주어진 입력 

0,1,1

0,0,1

0,1,0

을 그룹화 한 결과다.

빨간 글씨는 그룹의 번호이고

파란 글씨는 그룹(모양)의 크기이다.

 

위의 표에서 좌표 1,1에 있는 0을 탐색한다고 하자.

이 때 0은 4방향으로 탐색할 수 있으며,

0의 상 : 1그룹

0의 하 : 2그룹

0의 좌 : X

0의 우 : 1그룹

으로 0은 1그룹의 크기 3과 2그룹의 크기1 그리고 본인의 크기 1을 더해 크기가 5가 된다.

 

따라서 풀이 순서는 다음과 같다.

1. 주어진 입력의 1들을 그룹화하고, 크기를 저장한다.

2. 모든 0을 탐색하며, 가장 큰 모양을 찾는다.

 

처음엔 1들을 그룹화하는 것과, 0을 탐색하는 것을 한 배열에서 같이하게끔 구현해서 틀렸었다.

이를 최적화하는 과정에서 얍문님의 블로그를 참고하였다.

https://yabmoons.tistory.com/270 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

#define MAX (1000)

using namespace std;

int N, M;
int graph[MAX][MAX];
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int answer = 0;
int group = 1;
//visited.first = group visited.second = cnt
pair<int, int> visited[MAX][MAX];


//1인 칸들을 그룹화
void BFS(int r, int c) {
	queue<pair<int, int>> q, qq;
	q.push({ r,c });
	qq.push({ r,c });
	int cnt = 1;
	visited[r][c] = { group++,1 };
	while (!q.empty()) {
		int cr = q.front().first;
		int cc = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = cr + dir[i][0];
			int nc = cc + dir[i][1];
			if (nr >= 0 && nr < N && nc >= 0 && nc < M && graph[nr][nc] == 1 && visited[nr][nc].second == 0) {
				cnt++;
				visited[nr][nc].second = 1;
				q.push({ nr, nc });
				qq.push({ nr,nc });
			}
		}

	}
	while (!qq.empty()) {
		int cr = qq.front().first;
		int cc = qq.front().second;
		qq.pop();
		visited[cr][cc] = { group, cnt };
	}

}

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

	cin >> N >> M;
	vector<pair<int, int>> vt;
	//그래프 입력 및 0의 좌표들 저장 (변경할 칸의 좌표)
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
			if (graph[i][j] == 0)
				vt.push_back({ i,j });
		}
	}

	//1인 칸들 그룹화
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 1 && !visited[i][j].second)
				BFS(i, j);
		}
	}
	//0인 좌표들 탐색
	for (int i = 0; i < vt.size(); i++) {
		int r = vt[i].first;
		int c = vt[i].second;
		int cnt = 1;
		map<int, int> plus;
		for (int j = 0; j < 4; j++) {
			int nr = r + dir[j][0];
			int nc = c + dir[j][1];
			if (nr >= 0 && nr < N && nc >= 0 && nc < M &&graph[nr][nc] == 1) {
				plus[visited[nr][nc].first] = visited[nr][nc].second;
			}
		}
		for (auto o : plus) {
			cnt += o.second;
		}
		answer = max(answer, cnt);
	}

	cout << answer << '\n';
	return 0;
}