[G3] 백준 1941번 소문난 칠공주 C++ 백트래킹, 너비 우선 탐색

리뷰

 

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

백트래킹을 통해 조합을 찾고, 해당 조합이 유효한지 검증하는 문제

 

 

전역 변수

• ans : 정답을 저장할 변수
• lst : 학생의 파를 저장할 배열
• choose : 선택한 학생번호를 저장할 벡터
• way : 갈 수 있는 학생인지 여부를 저장할 2차원 배열
• v : 방문했던 학생인지 여부를 저장할 2차원 배열
• pick : 선택한 학생인지를 저장할 벡터
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 위치 정보 x, y를 정의할 구조체

 

함수

1. bt

void bt(int level, int cnt)

 

7명의 학생을 선택하는 조합을 찾는 함수

1. 매개 변수로 선택 가능한 학생의 시작 번호 level, 선택한 학생의 수 cnt를 전달 받는다.
2. 기저 조건으로 cnt가 7일 경우 chk, bfs함수를 호출해 모두 true라면 ans를 증가시킨 후 리턴한다.
3. level부터 24까지 for문으로 탐색하며 pick배열에 이미 선택한 학생은 continue처리해 준다.
4. 선택하지 않은 학생일 경우 선택 처리 후 choose에 학생 번호를 push하고, 재귀를 진행한다.
5. 재귀를 빠져나온 후엔 choose에서 마지막 학생 번호를 빼내고 방문을 해제해 준다.

 

2. chk

bool chk()

 

선택한 학생 중 이다솜파의 학생이 4명 이상한지 확인하기 위한 함수

1. 변수 cnt를 0으로 초기화 하고, choose벡터를 순회해 준다.
2. 각 학생 번호의 lst에 저장된 값이 1일 경우 cnt를 증가시킨다.
3. 탐색을 마친 후 cnt가 4이상이라면 true를, 아니라면 false를 리턴한다.

 

3. bfs

bool bfs()

 

너비 우선 탐색을 통해 선택한 7명의 학생이 연결되어 있는지를 확인하기 위한 함수

1. memset 함수를 통해 way, v배열을 0으로 초기화 해준다.
2. 선택한 학생을 순회하며 해당 학생의 좌표에 해당하는 way배열의 값을 true로 변경해 준다.
3. 변수 cnt를 1로 초기화 하고 Pos타입의 큐 q를 초기화하고, 첫 번째 학생의 좌표를 q에 push해준다.
4. v배열에 첫 번째 학생의 좌표를 방문처리 하고, q가 빌 때 까지 while 루프를 수행해 준다.
5. 매 루프마다 요소를 한개씩 꺼내어 주고 4방향 탐색을 진행해 준다.
6. 이동할 위치가 맵의 범위 안에있으며 way에서 true이고 방문하지 않는 지점이라면 이동을 진행한다.
7. 이동 후엔 방문처리 후 cnt를 1만큼 증가시키고 q에 이동한 좌표를 다시 push해준다.
8. while 루프가 종료된 후 cnt의 값이 7이라면 true를, 아니라면 false를 리턴해 준다.

 

문제풀이

1. 5 * 5크기의 맵을 입력 받고, 'S'인 경우 lst의 학생 번호에 1로 기록해 준다.
2. bt함수에 0, 0을 매개변수로 전달하여 호출해 준다.
3. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 백트래킹을 진행할 때 학생을 선택하거나 선택하지 않는 방법을 사용 후 제출했다가 Fail을 받았다.
2. 백트래킹 내부를 순서가 없는 조합을 선택하는 로직으로 변경 후 AC를 받았다.

 

참고 사항

1. 학생 7명을 뽑는 조합을 만든다.
2. 해당 조합에서 이다솜파가 4명 이상인지 체크한다.
3. 7명이 모두 인접해 있는지 확인한다.

 

정답 코드

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

int ans;
int lst[25];
vector<int> choose;
bool way[5][5], v[5][5], pick[25];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y;
};

bool bfs() {
	memset(way, 0, sizeof(way));
	memset(v, 0, sizeof(v));

	for (int i : choose) {
		int x = i / 5, y = i % 5;
		way[x][y] = true;
	}

	int cnt = 1;
	queue<Pos> q;
	q.push({ choose[0] / 5, choose[0] % 5 });
	v[choose[0] / 5][choose[0] % 5] = 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 < 5 && 0 <= ny && ny < 5 && way[nx][ny] && !v[nx][ny]) {
				v[nx][ny] = true;
				cnt++;
				q.push({ nx, ny });
			}
		}
	}
	return cnt == 7 ? true : false;
}

bool chk() {
	int cnt = 0;
	for (int i : choose) {
		if (lst[i]) cnt++;
	}
	return cnt >= 4 ? true : false;
}

void bt(int level, int cnt) {
	if (cnt == 7) {
		if (chk() && bfs()) ans++;
		return;
	}
	for (int i = level; i < 25; ++i) {
		if (pick[i]) continue;
		pick[i] = true;
		choose.push_back(i);
		bt(i + 1, cnt + 1);
		choose.pop_back();
		pick[i] = false;
	}
}

int main() {
	for (int i = 0; i < 5; ++i) {
		string s; cin >> s;
		for (int j = 0; j < 5; ++j) {
			if (s[j] == 'S') lst[i * 5 + j] = 1;
		}
	}
	bt(0, 0);
	cout << ans;
}