[G4] 백준 17141번 연구소 2 C++ 백트래킹, 너비 우선 탐색, 플러드필

리뷰

 

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

예제는 다 맞는데 이상하게 시간 초과와 틀렸습니다가 계속해서 출력되었던 문제

결국 사소한 변수 하나와 부등호 하나의 차이였다.

 

 

전역 변수

• n : 맵의 한 변의 길이를 저장할 변수
• m : 배치할 수 있는 바이러스의 개수를 저장할 변수
• l : 바이러스의 개수를 저장할 변수
• wall : 맵 상의 벽의 개수를 저장할 변수
• blank : 맵 상의 벽이 아닌 공간의 개수를 저장할 변수
• ans : 정답을 저장하기 위한 변수
• lst : 맵 정보를 저장할 2차원 정수 배열
• v : 방문 처리 및 소요 시간을 저장할 2차원 정수 배열
• dx, dy : 4방향 탐색을 진행하기 위한 방향 배열
• Pos : 좌표 정보를 정의하기 위한 구조체
• V : 바이러스의 좌표 정보를 저장하기 위한 Pos타입의 벡터

 

함수

1. bt

void bt(int level, int index, vector<Pos>& cur)

 

백트래킹을 통해 바이러스를 놓는 모든 경우를 탐색하기 위한 함수

1. 매개변수로 재귀 단계 level, 사용 가능한 바이러스의 인덱스 index, 바이러스 정보 cur을 전달받는다.
2. 기저 조건으로 level이 m에 도달했을 때 플러드필을 진행한다.
3. 우선 memset메서드를 통해 방문 배열 v를 초기화 한다.
4. floodfill 함수에 cur을 매개변수로 전달하고, 리턴 값을 변수 result에 입력 받는다.
5. ans와 result 중 작은 값을 ans에 저장한 후 리턴한다.
6. 기저조건에 해당하지 않을 경우 index번째 부터 l - 1번째 까지 for문을 개행한다.
7. cur에 V[i]를 추가하고, 재귀 단계 증가 및 index값을 i + 1로, cur을 전달하여 재귀를 진행한다.
8. 재귀를 빠져나오면 cur의 마지막 요소를 pop해준다.

 

2. floodfill

int floodfill(vector<Pos>& cur)

 

플러드 필을 통해 바이러스의 확산을 시뮬레이션 하기 위한 함수

1. 매개변수로 Pos타입의 벡터 cur을 참조로 받아준다.
2. 정수형 변수 remain에 blank값을 저장해 준다.
3. Pos타입의 큐 q를 초기화 한 뒤 cur내에 있는 요소를 q에 push해준다.
4. 각 바이러스의 위치를 방문처리 후 remain값을 감소시켜준다.
5. 정수형 변수 result를 0으로 초기화 해준다.
6. q가 빌 때 까지 while루프를 수행하고 매 루프마다 요소를 한개씩 꺼내어 준다.
7. 기저 조건으로 현재 방문처리된 값이 ans보다 클 경우 매우 큰 특정 값을 리턴한다.
8. 만약 현재 방문 처리된 값이 result보다 크다면 result에 해당 값을 저장한다.
9. 4방향 탐색을 진행하며, 벽이 아니고 방문처리 되지 않았다면 이동을 진행한다.
10. 이동 후에는 해당 위치에 이동한 위치의 방문 값 + 1으로 방문처리를 진행해 준다.
11. q에 해당 좌표를 push해주고, remain을 1만큼 감소시켜 준다.
12. 루프가 종료된 후 remain의 값이 0이라면 result - 1을, 아니라면 매우 큰 특정 값을 리턴한다.

 

문제풀이

1. n, m값을 입력 받고, n * n크기의 맵 정보를 입력 받아준다.
2. 입력 받은 값이 2일 경우 V에 해당 위치를 추가해 주고, 값을 0으로 변경해 준다.
3. 입력 받은 값이 1일 경우 wall을 증가시켜 준다.
4. 맵 정보를 모두 입력받은 후 blank를 n^2 - wall값으로 초기화 해준다.
5. 변수 l에 V의 크기를 저장해 준다.
6. Pos타입의 벡터 cur을 초기화 해준다.
7. bt함수에 level = 0, index = 0, cur을 매개변수로 전달하여 백트래킹을 진행한다.
8. 만약 ans의 값이 매우 큰 특정값이라면 -1을, 아니라면 ans를 출력한다.

 

트러블 슈팅

1. 재귀를 진행할 때 index + 1을 매개변수로 전달하여 시간 초과가 발생하였다.
2. index + 1을 i + 1로 수정한 후 시간 초과를 막을 수 있었다.
3. 플러드필의 기저 조건으로 v[cx][cy] >= ans를 해준 부분에서 틀렸습니다가 발생하였다.
4. 방문 값이 1로 시작하기 때문에 발생한 문제였다, v[cx][cy] > ans로 변경해 주니 AC를 받았다.

 

참고 사항

• 문제에서의 매우 큰 특정값은 모두 동일한 값이어야 한다.
• ans의 초기값, 플러드필의 기저조건 리턴 값, -1출력 여부는 모두 동일해야 한다.
• 나는 문제 풀이 시 2e9 즉 20억으로 세팅하였다.

 

정답 코드

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

int n, m, l, wall, blank, ans = 2e9;
int lst[50][50];
int v[50][50];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y;
};

vector<Pos> V;

int floodfill(vector<Pos>& cur) {
	queue<Pos> q;
	int remain = blank;
	for (const Pos& Pos : cur) {
		q.push({ Pos.x, Pos.y });
		v[Pos.x][Pos.y] = 1;
		remain--;
	}
	
	int result = 0;
	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;
		if (v[cx][cy] > ans) return 2e9;
		if (v[cx][cy] > result) result = v[cx][cy];

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && !lst[nx][ny] && !v[nx][ny]) {
				v[nx][ny] = v[cx][cy] + 1;
				q.push({ nx, ny });
				remain--;
			}
		}
	}
	return remain == 0 ? result - 1 : 2e9;
}

void bt(int level, int index, vector<Pos>& cur) {
	if (level == m) {
		memset(v, 0, sizeof(v));
		int result = floodfill(cur);
		ans = ans > result ? result : ans;
		return;
	}

	for (int i = index; i < l; ++i) {
		cur.push_back(V[i]);
		bt(level + 1, i + 1, cur);
		cur.pop_back();
	}
}

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 < n; ++j) {
			cin >> lst[i][j];
			if (lst[i][j] == 2) {
				V.push_back({ i, j });
				lst[i][j] = 0;
			}
			if (lst[i][j] == 1) wall++;
		}
	}
	blank = n * n - wall;

	l = V.size();
	vector<Pos> cur;
	bt(0, 0, cur);

	if (ans == 2e9) cout << -1;
	else cout << ans;
}