3187 양치기 꿍(C++)

같은 울타리 내에 우세종이 누군지 확인하고

전체 양과 늑대의 수를 구하는 문제

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

1. 문제

---

간단 설명

배열 맵이 주어진다. v는 늑대, k는 양을 의미한다.

울타리는 #로 표시된다

울타리는 영역으로 나누어지는데, 위 사진에는 총 6개의 영역이 있다

각 영역에서 늑대가 많다면 양은 다 잡아먹히고, 양이 더 많다면 늑대는 맞아죽는다

최종적으로 남은 늑대와 양의 수를 구하는 문제

2. 문제 분석

---

필요변수

맵을 저장할 배열 char map[MAX][MAX]

맵의 방문체크를 저장할 배열 int visited[MAX][MAX]

4방향 체크용 int direct[4][2]

일시적으로 늑대와 양의 수를 저장할 int wolf, sheep (최대 62,500)

최종적으로 정답을 저장할 int result_wolf, result_sheep

BFS를 이용할것이므로 큐.

주의점

• 늑대와 양의 수가 같으면 늑대가 이긴다
• 언제 BFS를 시작할 것인지

알고리즘

1. 맵을 입력받는다
2. 맵의 0,0 지점부터 시작해서, 방문하지 않았고, 울타리가 아니라면, 그 영역을 BFS 탐색 시작한다
    2-1. 큐에 시작지점을 넣고, 시작지점을 방문처리한다
    2-2. 큐가 빌때까지 다음 과정을 반복한다
        2-2-1. 큐의 맨 앞 원소를 꺼낸다
        2-2-2. 만약 늑대라면, 늑대 수를 1 증가시킨다
        2-2-3. 만약 양이라면, 양 수를 1 증가시킨다
        2-2-4. 4방향 탐색을 시도한다
            2-2-4-1. 만약 경계 밖이라면 패스
            2-2-4-2. 다음 셀이 울타리라면 패스
            2-2-4-3. 이미 방문한적 있다면 패스
            2-2-4-4. 위 과정을 통과했다면, 방문 처리 후, 큐에 넣는다
    2-3. 현재 울타리 영역의 탐색이 끝났다면, 체크한 늑대 수와 양의 수를 비교 후 우세종의 수를 증가시킨다
3. 모든 영역에 대한 BFS가 종료되면 결과값을 출력 후 종료

3. 소스코드

---

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

#define MAX 251

int R, C;
char map[MAX][MAX];
int visited[MAX][MAX];
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
int result_wolf = 0, result_sheep = 0;


void BFS(int starty, int startx) {
	queue<pair<int, int>> qu;
	qu.push({ starty, startx });
	visited[starty][startx] = 1;

	int wolf = 0, sheep = 0;

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		if (map[now.first][now.second] == 'v') {
			wolf++;
			map[now.first][now.second] = '.';
		}
		else if (map[now.first][now.second] == 'k') {
			sheep++;
			map[now.first][now.second] = '.';
		}

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.first;
			int dx = direct[t][1] + now.second;

			if (dy < 0 || dx < 0 || dy >= R || dx >= C) continue; // 경계 밖
			if (map[dy][dx] == '#') continue; // 울타리
			if (visited[dy][dx] == 1) continue;

			visited[dy][dx] = 1;
			qu.push({ dy,dx });
		}
	}

	if (wolf < sheep) {
		result_sheep += sheep;
	}
	else {
		result_wolf += wolf;
	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> R >> C;
	for (int y = 0; y < R; y++) {
		for (int x = 0; x < C; x++) {
			cin >> map[y][x];
		}
	}

	for (int y = 0; y < R; y++) {
		for (int x = 0; x < C; x++) {
			if (map[y][x] != '#' && visited[y][x] == 0)
				BFS(y, x);
		}
	}

	cout << result_sheep << " " << result_wolf << endl;


	return 0;
}