3184번: 양

https://www.acmicpc.net/problem/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

풀이

package graph_search;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_3184 {

    private static int width;
    private static int height;
    private static char[][] map;
    private static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private static boolean[][] visited;
    private static int numberOfLiveSheep;
    private static int numberOfLiveWolves;

    static class NumberOfAnimal {
        private int sheep;
        private int wolves;

        public int getSheep() {
            return sheep;
        }

        public int getWolves() {
            return wolves;
        }

        public void plusSheep() {
            sheep++;
        }

        public void plusWolves() {
            wolves++;
        }

        public boolean isZero() {
            return sheep == 0 && wolves == 0;
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        height = Integer.parseInt(st.nextToken());
        width = Integer.parseInt(st.nextToken());

        map = new char[width][height];
        visited = new boolean[width][height];

        for (int y = 0; y < height; y++) {
            String[] line = br.readLine().split("");

            for (int x = 0; x < width; x++) {
                map[x][y] = line[x].charAt(0);
            }
        }
    }

    private static void process() {
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                if (!visited[x][y] && map[x][y] != '#') {
                    NumberOfAnimal numberOfAnimal = new NumberOfAnimal();

                    dfs(x, y, numberOfAnimal);

                    updateResult(numberOfAnimal);
                }
            }
        }
    }

    private static void dfs(int startX, int startY, NumberOfAnimal numberOfAnimal) {
        int newX;
        int newY;
        char vertex = map[startX][startY];

        visited[startX][startY] = true;

        updateAnimal(numberOfAnimal, vertex);

        for (int i = 0; i < 4; i++) {
            newX = startX + direction[i][0];
            newY = startY + direction[i][1];

            if (!canGo(newX, newY)) {
                continue;
            }

            dfs(newX, newY, numberOfAnimal);
        }
    }

    private static boolean canGo(int newX, int newY) {
        if (newX < 0 || newY < 0 || newX >= width || newY >= height) {
            return false;
        }

        if (map[newX][newY] == '#') {
            return false;
        }

        if (visited[newX][newY]) {
            return false;
        }

        return true;
    }

    private static void updateAnimal(NumberOfAnimal numberOfAnimal, char vertex) {
        if (vertex == 'o') {
            numberOfAnimal.plusSheep();
        }

        if (vertex == 'v') {
            numberOfAnimal.plusWolves();
        }
    }

    private static void updateResult(NumberOfAnimal numberOfAnimal) {
        int numberOfSheep = numberOfAnimal.getSheep();
        int numberOfWolves = numberOfAnimal.getWolves();

        if (!numberOfAnimal.isZero()) {
            if (numberOfSheep > numberOfWolves) {
                numberOfLiveSheep += numberOfSheep;
            } else {
                numberOfLiveWolves += numberOfWolves;
            }
        }
    }

    private static void output() {
        System.out.println(numberOfLiveSheep + " " + numberOfLiveWolves);
    }

}