3187 : 양치기꿍

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

---

문제

양치기 꿍은 맨날 늑대가 나타났다고 마을 사람들을 속였지만 이젠 더이상 마을 사람들이 속지 않는다. 화가 난 꿍은 복수심에 불타 아예 늑대들을 양들이 있는 울타리안에 마구 집어넣어 양들을 잡아먹게 했다.

하지만 양들은 보통 양들이 아니다. 같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우 늑대가 전부 잡아먹힌다. 물론 그 외의 경우는 양이 전부 잡아먹히겠지만 말이다.

꿍은 워낙 똑똑했기 때문에 이들의 결과는 이미 알고있다. 만약 빈 공간을 '.'(점)으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 여러분은 몇 마리의 양과 늑대가 살아남을지 계산할 수 있겠는가?

단, 울타리로 막히지 않은 영역에는 양과 늑대가 없으며 양과 늑대는 대각선으로 이동할 수 없다.

입력

입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다.

다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다.

출력

살아남게 되는 양과 늑대의 수를 각각 순서대로 출력한다.

---

접근

• 벽이 아닌 구역별로 BFS 탐색을 한다. 
• 구역 내의 양과 늑대의 수를 센다. 
• BFS 탐색 후의 양과 늑대의 수를 비교하여, 규칙에 따라 최종 양과 늑대의 수를 결과값 변수에 넣는다. 
• BFS문제의 특징은, BFS함수의 기본 틀은 변하지 않고, 문제에서 요구하는 사항만 조금씩 변화해주면 된다는 것이다. 

---

코드

package beak;
 
import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M, countK, countV;
    static char[][] map;
    static boolean[][] visit;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, -1, 0, 1 };
 
    public static void BFS(int X, int Y) {
        Queue<Integer> qx = new LinkedList<Integer>();
        Queue<Integer> qy = new LinkedList<Integer>();
 
        qx.add(X);
        qy.add(Y);
 
        if (map[X][Y]!='#') {
            if (map[X][Y]=='k')
                countK++;
            if (map[X][Y]=='v')
                countV++;
            map[X][Y] = '#';
        }
 
        while (!qx.isEmpty() && !qy.isEmpty()) {
            X = qx.poll();
            Y = qy.poll();
            visit[X][Y] = true;
 
            for (int i = 0; i < 4; i++) {
                int nextX = X + dx[i];
                int nextY = Y + dy[i];
 
                if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) {
                    if (map[nextX][nextY]!='#' && visit[nextX][nextY] == false) {
                        if (map[nextX][nextY]=='k')
                            countK++;
                        if (map[nextX][nextY]=='v')
                            countV++;
 
                        qx.add(nextX);
                        qy.add(nextY);
                        visit[nextX][nextY] = true;
                        map[nextX][nextY] = '#';
                    }
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st=new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new char[N][M];
        visit = new boolean[N][M];
        int[] result = new int[2]; // result[1]은 양 , result[0]은 늑대의 결과 값을 넣을 배열 
 
        countK = 0;    // 양 
        countV = 0;    // 늑대 
 
        for (int i = 0; i < N; i++) {
            char[] tmp=br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                map[i][j] = tmp[j];
            }
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j]!='#') {
                    BFS(i, j);
                    if (countK > countV)
                        result[1] += countK;
                    else
                        result[0] += countV;
                }
                countK = countV = 0;
            }
        }
 
        bw.write(result[1] + " " + result[0] + "\n");
 
        bw.flush();
        br.close();
    }
}