(백준 / 완전탐색) 양치기 꿍

문제 요약

• R, C크기의 맵이 주어진다.(3<->250)
• 맵은 양, 늑대, 벽, 빈공간으로 이루어져있다.
• 벽으로 둘러쌓인 공간에서 양과 늑대 중 수가 많은 쪽이 살아남는다.
• 살아남은 양과 늑대의 수를 출력하라

원문

솔루션

BFS에 약간의 연산이 추가된 문제. 4방향 중 벽이 아닌 부분만 탐색하며 양과 늑대의 개수를 세면 된다. 재탐색하지 않도록 탐색이 끝난부분은 다른 문자열로 치환해준다.

상태공간

문제에서 요구하는 값은 살아남는 양과 늑대의 수이다. 벽으로 둘러쌓인 공간에서 살아남는 양과 늑대의 수를 상태공간으로 정의하면, 벽으로 둘러쌓인 공간 여러개를 탐색한 결과가 최종적으로 살아남는 양과 늑대의 수가 된다.

시간복잡도

\(250*250_{맵의 넓이, 높이} * 4_{상하좌우 탐색} = 5^4*10^2 * 2^2 = 250,000\)

구현 순서

1. map을 탐색
2. map[i][j]가 #이 아니면, i,j를 시발점으로 갖는 함수 f 시작
   1. i,j로부터 갈 수 있는 4방향을 탐색
   2. 양이나 늑대가 있으면 계산에 추가
   3. 갈 수 있는 좌표값을 탐색 큐에 추가
3. 전체 양, 늑대의 개수에서 탐색결과를 반영

코드

#include <iostream>
#include <queue>
using namespace std;
/*
* ARR : 양, 늑대, 빈공간, 벽 정보가 포함된 변수
* D : 4방향 좌표 델타값
* ans_k, ans_v : 살아남은 늑대(k)와 양(v) 수
*/
int M, N, D[4][2] = { {-1, 0}, {0, 1},{1, 0}, {0, -1} };
char ARR[251][251] = { 0, };

int ans_k = 0, ans_v = 0;

//f : ARR의 Y,X 좌표가 포함된 영역을 탐색하면서 양의 수와 늑대의 수를 세고 #으로 만들어서 재 탐색하지 않도록하라
void f(int Y, int X) {
	/*
	* ck, cv = 영역에서의 늑대, 양 수
	*/
	int ck = 0, cv = 0;

	queue<pair<int, int>> q;
	q.push(make_pair(Y, X));

	if (ARR[Y][X] == 'k') ck++;
	else if (ARR[Y][X] == 'v') cv++;

	ARR[Y][X] = '#';

	while (!q.empty()) {
		int cy = q.front().first, cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = D[d][0] + cy, nx = D[d][1] + cx;
			if (ARR[ny][nx] == '#' || ny <1 || ny > M || nx < 1 || nx > N) continue;

			if (ARR[ny][nx] == 'k') ck++;
			else if (ARR[ny][nx] == 'v') cv++;

			q.push(make_pair(ny, nx));
			ARR[ny][nx] = '#';
		}
	}

	if (ck > cv) ans_k += ck;
	else ans_v += cv;
}
int main() {
	int i, j;
	cin >> M >> N;
	for (i = 1; i <= M; i++) for (j = 1; j <= N; j++) cin >> ARR[i][j];
	for (i = 1; i <= M; i++) for (j = 1; j <= N; j++) if (ARR[i][j] != '#')f(i, j);
	cout << ans_k << " " << ans_v << endl;
}