[G3] 백준 16988번 Baaaaaaaaaduk2 (Easy)

리뷰

 

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

백트래킹 + 너비 우선 탐색을 통해 해결한 문제

 

 

전역 변수

• n, m : 맵의 세로/가로 길이를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 초기 맵 정보를 저장할 2차 배열
• bool : 방문 여부를 체크할 2차 배열
• Pos : 시뮬레이션 시 사용하기 위한 구조체, 위치 정보 x, y를 정의한다.
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. bt

void bt(int level, int x, int y)

 

백트래킹을 통해 흰색 돌을 둘 수 있는 모든 경우를 구하는 함수

1. 매개 변수로 재귀 단계 level, 이전에 돌을 둔 위치 x, y를 전달 받는다.
2. 기저 조건으로 재귀 단계가 2에 도달한 경우 solve함수를 호출하고, 리턴 값과 ans를 비교해 최값을 갱신 후 리턴한다.
3. 기저 조건이 아닌 경우 x, y 이후 부터 탐색하며 빈 땅을 만난 경우 1로 변경 후 재귀를 수행하고, 빠져나오며 다시 0으로 변경한다.

 

2. solve

int solve()

 

잡을 수 있는 검은 돌의 개수를 구하기 위한 함수

1. memset을 통해 방문 배열 v를 초기화 해주고, 변수 result를 0으로 초기화 해준다.
2. n * m크기를 순회하며 2를 만났고, 방문 처리가 되어있지 않은 경우 bfs함수에 좌표를 전달해 그룹화를 진행한다.
3. 함수의 결과값을 result에 더하고, 모든 그룹화를 진행한 경우 result에 저장된 값을 출력한다.

 

3. bfs

int bfs(int sx, int sy)

 

검은 돌이 흰색 돌로 에워싸져 있는지 확인하기 위한 함수

1. 매개 변수로 탐색 시작 위치 sx, sy를 전달 받는다.
2. Pos타입의 큐 q를 초기화 하고 시작 위치를 push해준다.
3. 시작 위치에 방문 처리를 해주고, 변수 cnt는 1로, result는 true로 초기화 해준다.
4. q가 빌 때 까지 while 루프를 돌며 매 루프마다 요소를 한개씩 빼내어 준다.
5. 4방향 탐색을 진행하며, 맵의 범위에 있고, 흰돌이 아니며, 방문처리 되어 있지 않다면 이동을 진행한다.
6. 만약 빈 땅인 경우 result가 false인 경우 continue, true인 경우 false로 변경 후 continue처리해 준다.
7. 이동 후엔 방문처리 후 cnt를 증가시키고, 큐에 이동한 위치를 push해준다.
8. while루프가 종료된 후 result가 true라면 cnt를, false라면 0을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵 정보를 lst배열에 입력 받아준다.
2. n * m크기의 맵을 순회하며 빈 땅인 경우 1로 변경 후 bt함수에 매개변수 1, i ,j를 넣어 백트래킹을 시작한다.
3. 재귀가 종료된 후 1로 변경한 땅을 다시 0으로 변경해 준다.
4. 모든 탐색이 종료된 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 20 * 20크기의 맵이 모두 빈 경우 399 + 398 + 397 + ... + 1의 경우의 수가 있고, 매 로직 마다 memset, 브루트 포스 탐색을 통해 400 + 400의 시간 복잡도가 소요된다.
• 이 외에도 재귀 레벨이 2밖에 되지 않아 시간이 터질 일은 없다고 판단하였다.

 

정답 코드

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

int n, m, ans;
int lst[20][20];
bool v[20][20];
struct Pos {
	int x, y;
};
int dx[] = { 1, -1, 0 ,0 };
int dy[] = { 0, 0, 1, -1 };

int bfs(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy });
	v[sx][sy] = true;
	int cnt = 1;
	bool result = true;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != 1 && !v[nx][ny]) {
				if (lst[nx][ny] == 0) {
					if (!result) continue;
					else {
						result = false;
						continue;
					}
				}
				v[nx][ny] = true;
				cnt++;
				q.push({ nx, ny });
			}
		}
	}
	return result ? cnt : 0;
}

int solve() {
	memset(v, 0, sizeof(v));
	int result = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (lst[i][j] == 2 && !v[i][j]) {
				result += bfs(i, j);
			}
		}
	}
	return result;
}

void bt(int level, int x, int y) {
	if (level == 2) {
		ans = max(ans, solve());
		return;
	}

	for (int i = x; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i == x && j <= y) continue;
			if (!lst[i][j]) {
				lst[i][j] = 1;
				bt(level + 1, i, j);
				lst[i][j] = 0;
			}
		}
	}
}

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

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

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (!lst[i][j]) {
				lst[i][j] = 1;
				bt(1, i, j);
				lst[i][j] = 0;
			}
		}
	}
	cout << ans;
}