[백준] 3184번 양

문제

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

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

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

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

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

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

입력

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

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

출력

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

 

이 문제는 생각보다 쉬운 bfs문제다.

이제 슬슬 bfs는 적응한것 같다...

물론 어려운 문제는 어떻게 푸는지 잘 모르는 경우도 있지만....

 

 

양과 늑대의 수만 잘 세어주면 무리없이 맞출 수 있는 문제다.

예제를 잘 보면 울타리가 있는데.. 그곳으로 둘러 쌓인게 영역이다. 그러니까 전체가 영역이라 생각할 수 있는데

울타리로 둘러쌓인게 영역이니까

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

예제 1번 같은 경우를 보면

영역이 총 6개다. 위에 하나 그 옆으로 또 하나 옆으로 하나 이렇게 맨 윗줄은 3개

밑에 2개가 있고.. 그 밑에 한개가 있다.

 

이런거로 미뤘을때,

늑대랑 양의 숫자에 따라 경우가 달라진다.

  1) 양이 1마리라도 더 많을 경우 : 양이 이김 ... 결국 늑대는 죽음

  2) 그게 아니라면 양이 죽음...

 

위 그림을 토대로 봤을때 늑대 1마리와 양 1마리가 보인다. 그렇기 때문에 양은 잡아 먹힌다.

하지만 늑대 2마리는 죽지 않기 때문에 양 : 0마리 늑대 : 2마리가 된다.

 

package _2020_06_08.C;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node {
	int x;
	int y;
	
	Node(int x,int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int R;
	static int C;
	
	static int sheep;
	static int wolf;
	
	static String maps[];
	
	static char dist[][];
	
	static boolean[][] visit;
	
	
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,-1,1};
	static void bfs(int i,int j){
		
		int curWolf = 0;
		int curSheep = 0;
		
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(i, j));
		visit[i][j] = true;
		
		if (dist[i][j] == 'o') {
			curSheep++;
		}
		
		if (dist[i][j] == 'v') {
			curWolf++;
		}
		while(!q.isEmpty()) {
			Node node = q.poll();
			int x = node.x;
			int y = node.y;
			
			for(int k = 0; k<4;k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				
				if (nx < 0  || R <= nx  || ny < 0 || C <= ny) continue;
				if (visit[nx][ny]) continue;
				
				if (dist[nx][ny] == '#') continue;
				
				if (dist[nx][ny] == 'o') {
					curSheep++;
				}
				
				if (dist[nx][ny] == 'v') {
					curWolf++;
				}
				
				visit[nx][ny] = true;
				q.add(new Node(nx, ny));
				
	
			}
			
		}
		
		if (curSheep > curWolf) {
			wolf -= curWolf;		
		} else {
			sheep -= curSheep;
		}
	}
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		
		R = sc.nextInt();
		C = sc.nextInt();
		
		maps = new String[R+1];
		dist = new char[R+1][C+1];
		visit = new boolean[R+1][C+1];
		
		for(int i = 0;i<R;i++) {
			maps[i] = sc.next();
			for(int j = 0; j < maps[i].length(); j++ ) {
				dist[i][j] = maps[i].charAt(j);
			}
			
		}
		

		for(int i = 0; i<R;i++) {
			for(int j = 0; j<C;j++) {
				if (dist[i][j] == 'o') {
					sheep++;
				}
				
				if (dist[i][j] == 'v' ) {
					wolf++;
				}
			}
		}
		
		for(int i = 0; i<R;i++) {
			for(int j = 0; j<C;j++) {
				
				if (visit[i][j]) continue;
				
				if (dist[i][j] == 'o' || dist[i][j] == 'v') {
					bfs(i,j);
				}
			}
		}
		
		System.out.println(sheep + " "+  wolf);
		
	}

}

솔직히 다른 분의 글을 참조해서 풀긴했다..ㅜㅜ

지금 생각해보면 토마토였나... 그 문제랑 굉장히 유사한듯 싶다.

아직 순수 그래프쪽은 힘든데... bfs쪽은 할만한것 같다.

 

예제가 서로 붙어 있기 때문에 String으로 해야함을 느꼈다. 그래서 String으로 했는데 자꾸 .charAt을 쓰는게 너무 귀찮아서 그것들을 전부 char로 바꿔서 넣어 버렸다. 안해도 되는데... 나는 귀찮음 방지로 넣었다.

 

 

그리고 전체 늑대랑 양을 세야 한다. 왜냐하면 죽임을 당하는 기 때문이다.

 

그리고 bfs를 이렇게 돌리는 이유는 딱히 없는데... 그냥 합치는게 편하잖아.!

o할때도 돌려도 되고... v일때도 돌려도 된다. 근데 그곳에 방문하면 안된다.

왜냐하면 양을 셋는데 또 세면 안대니까... 중복ㅜ

 

자 이제 bfs를 대충 만들고 이건 사람마다 다드게 만들 것 같다.

bfs의 특징이 퍼진다는게 특징인데...

퍼지면서 양을 세고 늑대도 센다... 그러다 보면

울타리에 걸려서 더이상 세지 못하는 경우도 발생된다.

어차피 울타리니까... (밑에다 그걸 설정해도 나쁘지는 않을 것 같다. 근데 굳이?)

 

 

 

자 이제 bfs가 끝났다. 그러면 울타리안에 양과 늑대가 몇마리인지 확인이된다.

그걸 조건에 맞게 빼주면 된다.

 

이걸 전체를 다 방문할때까지 반복해주면 끝!

세세한 로직보다는 이런식으로 동작하는게 도움이 될것 같아 이렇게 작성해 보았다.

 

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
int r, c;
vector<string> field;
bool check[255][255];
int my[] = { 0, 1, 0, -1 };
int mx[] = { 1, 0, -1, 0 };

void dfs(int y, int x, int& w, int& s)
{
	if (check[y][x] == true) return;

	check[y][x] = true;
	if (field[y][x] == 'v') w++;
	else if (field[y][x] == 'o') s++;

	for (int k = 0; k < 4; k++)
	{
		int ny = y + my[k];
		int nx = x + mx[k];

		if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
		if (field[ny][nx] == '#') continue;
		dfs(ny, nx, w, s);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> r >> c;
	field.resize(r);

	for (int i = 0; i < r; i++)
		cin >> field[i];

	int area = 1;
	int w, s;
	int wolves = 0, sheep = 0;

	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
		{
			if (field[i][j] != '#')
			{
				w = s = 0;
				dfs(i, j, w, s);
				if (s > w) sheep += s;
				else wolves += w;
			}
		}

	cout << sheep << " " << wolves << endl;
	return 0;
}

 

 

맞어. 내가 자바로 풀었다는걸 까먹고 있었군... 뭐 c든 자바든 그건 중요한게 아니지만...