[Java] 백준 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

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int R, C, sheepN, wolfN;
	private static char[][] map;
	private static boolean[][] visited;
	private static int []dx= {-1,1,0,0};
	private static int []dy= {0,0,-1,1};

	static class Point {
		int r, c;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		visited = new boolean[R][C];

		for (int r = 0; r < R; r++) {
			String s = br.readLine();
			for (int c = 0; c < C; c++) {
				map[r][c] = s.charAt(c);
			}
		}

		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (!visited[r][c] && map[r][c] != '#') {	// 울타리가 아니고 아직 방문하지 않았으면 영역 탐색
					bfs(r, c);
				}
			}
		}
		sheepN=0;
		wolfN=0;
		for(int r=0;r<R;r++) {
			for(int c=0;c<C;c++) {
				if(map[r][c]=='o') sheepN++;	// 양의 수 카운트
				if(map[r][c]=='v') wolfN++;	// 늑대의 수 카운트
			}
		}
		System.out.println(sheepN+" "+wolfN);
	}

	private static void bfs(int r, int c) {
		Queue<Point> queue=new LinkedList<>();
		queue.add(new Point(r, c));
		
		visited[r][c]=true;
		List<Point> sheep=new ArrayList<>();
		List<Point> wolf=new ArrayList<>();
		if(map[r][c]=='o') sheep.add(new Point(r, c));
		if(map[r][c]=='v') wolf.add(new Point(r, c));
		while(!queue.isEmpty()) {
			Point p=queue.poll();
			
			for(int d=0;d<4;d++) {
				int nx=p.r+dx[d];
				int ny=p.c+dy[d];
				
				if(isIn(nx, ny) && !visited[nx][ny] && map[nx][ny]!='#') {
					visited[nx][ny]=true;
					if(map[nx][ny]=='o') sheep.add(new Point(nx, ny));	// 양인 경우 양 리스트에 저장
					if(map[nx][ny]=='v') wolf.add(new Point(nx, ny));	// 늑대인 경우 늑대 리스트에 저장
					queue.add(new Point(nx, ny));
				}
			}
		}
		if(sheep.size()>wolf.size()) {	// 양의 수가 더 많으면 늑대를 쫓아냄
			for(int i=0;i<wolf.size();i++) {
				Point p=wolf.get(i);
				map[p.r][p.c]='.';
			}
		} else {	// 늑대의 수가 더 많거나 같으면 양을 잡아먹음
			for(int i=0;i<sheep.size();i++) {
				Point p=sheep.get(i);
				map[p.r][p.c]='.';
			}
		}
	}

	private static boolean isIn(int r, int c) {
		return r >= 0 && r < R && c >= 0 && c < C;
	}
}