[C++] BOJ(백준) 1926 그림

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

1926번: 그림

BFS 문제다.

 

이어져 있는 1들을 찾기 위해서는 BFS, 연속된 1이 몇 묶음(?) 있는지 알기 위해서는 단순하게 부르트포스를 이용했다.

보통 BFS를 사용할 때는 board 배열, visit 배열 두 개 를 사용한다.

이 문제에서는 입력이 0과 1만 들어오고, 원본을 유지해야 할 필요가 없으므로

visit 배열을 선언하지 않고 board배열의 값을 바꿔주었다. (방문 시 1을 0으로)

 

1 탐색을 좌측상단에서 시작해 우측하단으로 가기 때문에 BFS에서 왼쪽과 위쪽은 탐색할 필요가 없다고 생각했다.

그러나 7%까지 밖에 가지 못하고 처참하게 틀렸습니다를 마주했다.

(이에 대한 고민은 조금 더 생각을 해봐야 할 것 같다)

 

연속된 1의 개수 (그림의 크기)를 구하기 위해서는 board의 1을 0으로 바꿔줄 때 카운트 한 뒤 값을 리턴했다.

최종 코드는 메인에서 배열을 모두 탐색하여 값이 1일 떄 BFS를 수행했다.

 

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

int n, m;
int arr[500][500];
// 상하좌우 탐색을 위한 좌표
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int BFS(int x, int y) {
	int cnt = 1;	// 그림의 크기를 구하기 위한 변수
	queue<pair<int, int>> q;

	// 처음 방문 구간
	arr[x][y] = 0;
	q.push(make_pair(x, y));

	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();

		// 상하좌우 4번 탐색을 하기 위함
		for (int i = 0; i < 4; i++) {
			int xx = cur.first + dx[i];
			int yy = cur.second + dy[i];

			// 좌표가 범위를 벗어날 경우 continue
			if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
			// 방문한 적이 있으면 continue
			if (!arr[xx][yy]) continue;

			// 방문 표기 후, 큐에 push
			arr[xx][yy] = 0;
			q.push(make_pair(xx, yy));
			cnt++;
		}
	}
	return cnt;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) cin >> arr[i][j];

	int cnt = 0;	// 그림의 개수
	int max = 0;	// 그림의 최대 크기

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			// 배열의 값이 1이면 BFS 실행
			if (arr[i][j]) {
				int a = BFS(i, j);
				if (max < a) max = a;
				cnt++;
			}

	cout << cnt << "\n" << max;
}

앞서 설명한 내용의 board를 arr로 사용하였다.