백준 온라인 저지 | 1926번 그림 | C++

백준 온라인 저지 | 1926번 그림 | C++

1926번: 그림

 

1. 문제 접근

■ 1.1 4방위 너비 우선 탐색

 2차원 평면에서 0과 1로 그림의 데이터가 주어진 상태에서 1과 상하좌우로 연결된 (대각선으로는 연결되지 않은) 그림의 개수와 그 그림 중에서 가장 넓이가 큰 그림의 넓이를 출력해야 한다. 1과 인접한 상하좌우를 순서대로 탐색해야 하므로 큐(queue) 자료구조를 이용하여 4방위 너비 우선 탐색을 하고자 한다.

 

■ 1.2 그림의 개수와 그림의 넓이

 숫자 1로 상하좌우 연결된 그림의 개수와 그 그림 중에서 가장 넓이가 큰 그림을 찾아내야 한다. 그림의 개수를 구하려면 모든 정점을 순회하면서 너비 우선 탐색을 시도하는 dfsAll 함수에서 dfs 함수를 호출하기 직전에 그림의 개수를 카운트하면 된다. 그림의 넓이는 너비 우선 탐색을 구현하는 dfs 함수에서 큐에 담아두었던 정점을 pop할 때마다 그림의 넓이를 1만큼 카운트하고, 큐가 비어있어 while문을 빠져나오면 1로 연결된 한 그림을 모두 너비 우선 탐색하였으므로 그 그림의 넓이를 구할 수 있다.

 

2. 문제 풀이

1. 도화지 정보를 저장할 2차원 벡터 adj와 정점에 방문했는지를 저장할 2차원 벡터 visited를 선언한다. adj와 visited의 크기는 N×M으로 설정하고 주어진 도화지 정보로 adj를 초기화한다.
2. 이중 for문으로 adj의 모든 정점을 순회하면서 너비 우선 탐색한다. 이때 정점이 0이거나 방문한 적이 있는 경우 다음 정점으로 바로 건너뛴다. 그리고 너비 우선 탐색을 시작할 때마다 그림의 개수를 센다.
3. 너비 우선 탐색할 정점이 숫자 1이고 방문한 적이 없는 경우 정점을 큐에 넣는다. 그리고 큐에서 정점을 꺼내 for문으로 사방위 정점을 순서대로 너비 우선 탐색한다.
   • 사방위 정점이 배열의 범위를 벗어나거나, 이미 방문한 정점이거나, 0인 경우 다음 정점으로 건너뛴다.
   • 그 외 정점은 visited에 방문 표시를 하고 큐에 넣는다. 그리고 큐에서 정점을 꺼내 위 과정을 반복한다.
4. 모든 정점에 대해 너비 우선 탐색이 종료된 후 그림의 개수와 그림의 최대 넓이를 출력한다.

 

3. 문제 해결

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

void makeGraph();
void bfsAll();
void bfs(int x, int y);

// 인접 행렬로 도화지를 표현합니다.
vector<vector<int>> adj;
// 정점의 방문 여부를 유지합니다.
vector<vector<bool>> visited;
// 너비 우선 탐색에 사용할 큐입니다.
queue<pair<int, int>> q;

int N, M;
int maxOfDrawing;
int numOfDrawing;
// 인접한 상하좌우 정점의 좌표를 만드는 데 사용합니다.
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	makeGraph();
	bfsAll();
	return 0;
}

// 주어진 도화지 정보로 인접 행렬을 만듭니다.
void makeGraph() {
	maxOfDrawing = 0;
	numOfDrawing = 0;
	// adj와 visited의 크기를 N * M으로 설정합니다.
	cin >> N >> M;
	adj = vector<vector<int>>(N, vector<int>(M, 0));
	visited = vector<vector<bool>>(N, vector<bool>(M, false));

	// 주어진 도화지 정보로 adj를 초기화합니다.
	for (int x = 0; x < N; ++x) {
		for (int y = 0; y < M; ++y) {
			cin >> adj[x][y];
		}
	}
}

// 모든 정점에 대해 깊이 우선 탐색을 수행합니다.
void bfsAll() {
	for (int x = 0; x < N; ++x) {
		for (int y = 0; y < M; ++y) {
			// 정점의 좌표가 0이거나 이미 방문한 경우 다음 정점으로 건너뜁니다.
			if (!adj[x][y] || visited[x][y]) {
				continue;
			}
			// 그외 정점은 깊이 우선 탐색을 수행합니다.
			// 그림의 개수를 1만큼 셉니다.
			++numOfDrawing;
			bfs(x, y);
		}
	}
	cout << numOfDrawing << '\n' << maxOfDrawing << '\n';
}

// 깊이 우선 탐색 알고리즘을 구현합니다.
void bfs(int x, int y) {
	// 깊이 우선 탐색을 시작할 정점을 큐에 집어넣습니다.
	visited[x][y] = true;
	q.push({ x, y });

	int sizeOfDrawing = 0;
	while (!q.empty()) {
		// 큐에서 정점을 꺼냅니다.
		pair<int, int> pos = q.front();
		q.pop();
		// 그림의 크기를 1만큼 셉니다.
		++sizeOfDrawing;

		// 사방위 정점을 확인합니다.
		for (int i = 0; i < 4; ++i) {
			// 사방위 정점의 좌표를 직접 생성합니다.
			int nx = pos.first + dx[i];
			int ny = pos.second + dy[i];
			// 새 정점의 좌표가 배열의 범위를 벗어나는 경우 다음 정점으로 건너뜁니다.
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) {
				continue;
			}
			// 새 정점의 좌표가 0이거나 이미 방문한 경우 다음 정점으로 건너뜁니다.
			if (!adj[nx][ny] || visited[nx][ny]) {
				continue;
			}
			// 그외 정점은 큐에 집어넣습니다.
			visited[nx][ny] = true;
			q.push({ nx, ny });
		}
	}
	// 그림의 최댓값을 비교하여 가장 큰 그림의 크기를 저장합니다.
	maxOfDrawing = max(maxOfDrawing, sizeOfDrawing);
}

 

1926번 그림 성공

 

4. 문제 고찰

■ 4.1 너비 우선 탐색

 1926번 그림은 너비 우선 탐색으로 구현하는 기본적인 문제이다. 너비 우선 탐색의 기본형을 다루므로 다른 BFS 문제를 해결하려면 이 알고리즘을 꼭 기억하고 있어야 한다.