백준 3184번 양 C++

오늘은 백준 3184번 양 문제를 풀어봤습니다

우선 문제를 확인해보면 예제에 행렬 리스트를 입력하고 있으면서
퍼져 나가는 느낌으로 탐색하는 탐색 문제임을 알 수 있습니다.

그럼 핵심적으로 체크해주어야 할 것들에 대해 생각해보도록 하겠습니다

1. 양과 늑대의 수 비교
   • 양의 수 > 늑대의 수 = 양의 수 추가
   • 양의 수 < 늑대의 수 = 늑대의 수 추가
2. 이미 방문한 곳들 check
3. 벽은 넘을 수 없으니 벽이 나오면 check
   • 이동할 위치를 체크해주면 됨

이렇게 3가지를 참고해 해결하도록 하겠습니다,

먼저 행렬 리스트를 받아줍니다

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

이후 첫 탐색 좌표를 받아오고 그 영역안에 있는 양의 수와 늑대의 수를 초기화해줍니다

queue<pair<int, int>> q;
visited[y][x] = 1; // 방문 체크
q.push({y, x});

int sheep = 0;
int wolf = 0;

상, 하, 좌, 우 4방향을 탐색해줍니다, 이때 이미 방문하거나 탐색할 위치가 울타리일 경우 continue를 통해 넘어가줍니다

while(q.size()) { // 이것을 통해 계속 반복
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || 
        ny >= n || 
        nx < 0 || 
        nx >= m || 
        visited[ny][nx]) continue;

	}
}

만약 방문하지도 않았고 울타리도 아니라면 방문 체크를 한 후 탐색 위치에 양또는 늑대가 있을 경우 count 해줍니다,

visited[ny][nx] = 1;
if (arr[ny][nx] == 'o') sheep++;
if (arr[ny][nx] == 'v') wolf++;

끝으로 queue에 탐색한 값을 push해 예외처리(방문 했거나, 울타리 이거나, 크기를 넘어가거나 등)가 날때까지 탐색을 반복해줍니다

q.push({ny, nx});

해당 영역에 대한 모든 탐색이 끝났다면 양의 수와 늑대의 수를 비교한 후 카운트 해줍니다

if (sheep > wolf) totalSheep += sheep;
else totalWolf += wolf;

다시 main 함수로 돌아와 모든 좌표에 대한 탐색을 해주고 만약 방문했다면 continue 해줍니다.

for (int i = 0; i < n; i++){
	for (int j = 0; j < m; j++){
		if (visited[i][j]) continue;
		bfs(i, j);
	}

}

마지막으로 출력을 해주면 됩니다

cout << totalSheep << " " << totalWolf << '\n';

풀어본 느낌으로는 BFS와 관련된 가장 기초적인 문제를 푼 후 수도 코드를 참고하고 푼다면 엄청 좋을듯한 문제였습니다, 감사합니다.

모든 코드

#include <bits/stdc++.h>

using namespace std;

int visited[251][251];
char arr[251][251];
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, totalSheep, totalWolf;

void bfs(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({y, x});
	
	int sheep = 0;
	int wolf = 0;
	
	while(q.size()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue;
			if (arr[ny][nx] == '#') continue;
			visited[ny][nx] = 1;
			if (arr[ny][nx] == 'o') sheep++;
			if (arr[ny][nx] == 'v') wolf++;
			q.push({ny, nx});
		}
	}
	
	if (sheep > wolf) totalSheep += sheep;
	else totalWolf += wolf;
	
}

int main() {
	
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) { 
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (visited[i][j]) continue;
			bfs(i, j);
		}
	}
	
	cout << totalSheep << " " << totalWolf << '\n';
	
	
	return 0;
}