백준 1012번: 유기농 배추

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

1012번: 유기농 배추

 

개요

2차원 배열에서 0이 아닌 군집의 갯수를 세는 문제이다.

 

군집의 확장은 상하좌우 방향으로 이루어지며, 대각선 방향의 확장은 고려하지 않는다.

 

 

문제 해석

주어지는 입력값을 입력받아, 이차원 행렬로 저장한다.

그리고 이차원 행렬을 전부 순차탐색하여 배추가 있음(행렬에서의 1)을 확인하면, 해당 위치 주위로 군집화를 확인한다.

군집화 확인은 BFS 알고리듬을 사용하며, 군집이 확인될 때 마다 해당값을 0으로 변경한다.

 

문제 풀이

배열의 순차 탐색 코드는 다음과 같다.

for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (map[i][j] == 1) {
			check_map(map, i, j, n, m);
			count++;
		}
	}
}

기본적인 순차탐색 코드로 배추가 있음(value == 1)을 확인하면 함수를 호출하였다.

 

check_map 함수는 다음과 같다.

void check_map(vector<vector<int>> &map, int x, int y, int n, int m) {
	int dx[] = { 0,0,1,-1 };
	int dy[] = { 1, -1, 0, 0 };

	vector<vector<int>> visit(n, vector<int>(m, 0));

	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visit[x][y] = 1;
	while (!q.empty()) {
		auto current = q.front();
		q.pop();
		map[current.first][current.second] = 0;
		for (int i = 0; i < 4; i++) {
			int next_x = current.first + dx[i];
			int next_y = current.second + dy[i];
			if (next_x < 0 || next_y<0 || next_x >=n || next_y >= m)
				continue;
			
			if (map[next_x][next_y] == 1 && visit[next_x][next_y] == 0) {
				q.push(make_pair(next_x, next_y));
				visit[next_x][next_y] = 1;
			}
		}
	}
}

 

벡터 이차원 배열인 map은 참조 호출로 가져와 변경이 일어나도록 한다.

그리고 기본적인 BFS와 동일하게 큐에 시작 값을 PUSH하고,

큐가 empty 상태가 될 때 까지 값을 하나씩 POP하고 해당 위치는 0으로 변경한다.

POP한 위치에 대해서는, 해당 위치의 상하좌우에 인접한 배추를 발견하면 해당 위치를 다시 큐에 넣도록 한다.

해당 작업을 전부 마치면 군집 하나가 전부 0으로 바뀌었으므로, 함수를 종료하면 된다.

 

 

처음 이 문제를 풀 때는 메모리 초과가 발생하였는데, 이는 BFS의 기초인 방문 지점 check를 하지 않아 발생하였다.

vector<vector<int>> visit(n, vector<int>(m, 0));

위의 visit 이차원 배열을 이용하여, 방문한 위치에 대해서는 push를 진행하지 않도록 하는 것이 포인트다.

// 방문 체크가 없는 코드
if (map[next_x][next_y] == 1) {
	q.push(make_pair(next_x, next_y));
}

// 방문 체크가 있는 코드
if (map[next_x][next_y] == 1 && visit[next_x][next_y] == 0) {
	q.push(make_pair(next_x, next_y));
	visit[next_x][next_y] = 1
}