[백준] 양 (3184번)

문제

미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.

마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.

다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.

맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.

아침이 도달했을 때 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다.

다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.

출력

하나의 줄에 아침까지 살아있는 양과 늑대의 수를 의미하는 두 정수를 출력한다.

예제 입력 1 복사

6 6 ...#.. .##v#. #v.#.# #.o#.# .###.# ...###

예제 출력 1 복사

0 2

예제 입력 2 복사

8 8 .######. #..o...# #.####.# #.#v.#.# #.#.o#o# #o.##..# #.v..v.# .######.

예제 출력 2 복사

3 1

예제 입력 3 복사

9 12 .###.#####.. #.oo#...#v#. #..o#.#.#.#. #..##o#...#. #.#v#o###.#. #..#v#....#. #...v#v####. .####.#vv.o# .......####.

예제 출력 3 복사

3 5

---

기본적인 bfs 문제이다.

맵의 모든 방문하지 않은 지점을 방문하면서, 늑대와 양의 수를 센다.

주의할 점은 같은 울타리 안에서 양의 수가 더 많다면 늑대를 이기고, 반대는 늑대가 이긴다. 

따라서 울타리 내에서 늑대나 양 중 한 종류만 살아남게 된다.

모든 지점을 방문하면서 전체 양과 늑대의 수를 세고 출력하면 된다.

코드만으로 이해가 되는 쉬운 문제이다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%96%91%20(3184%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <queue>
using namespace std;
int R, C;
int visit[251][251];
char p[251][251];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
int O, V;

void bfs(int a, int b) {
	queue<pair<int, int>> q;
	q.push({ a,b });
	visit[a][b] = 1;
	int curO = 0, curV = 0;
	if (p[a][b] == 'o') curO++;
	else if (p[a][b] == 'v') curV++;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<0 || ny <0 || nx>R || ny>C) continue;
			if (p[nx][ny] == '#') continue;
			if (visit[nx][ny] == 1) continue;
			visit[nx][ny] = 1;
			q.push({ nx,ny });
			if (p[nx][ny] == 'o') curO++;
			else if (p[nx][ny] == 'v') curV++;
		}
	}

	if (curO > curV) O += curO;
	else V += curV;
	return;
}

int main()
{
	cin >> R >> C;
	for (int i = 0; i < R; i++) 
		for (int j = 0; j < C; j++) 
			cin >> p[i][j];

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if (visit[i][j] == 0 && p[i][j] != '#') bfs(i, j);

	cout << O << " " << V;
}