[BOJ] 3184번 양 자바

문제

https://www.acmicpc.net/problem/3184

3184번: 양

문제

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

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

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

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

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

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

입력

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

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

출력

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

풀이

#bfs

배열 전체에 대해 이중반복문을 돌면서 bfs를 사용해 각 영역별 늑대와 양의 수를 구한다.

울타리를 기준으로 영역이 나뉘기 때문에 방문하지 않은 경우와 #(울타리)가 아닌 경우에 bfs를 실행한다.

현재 방문한 노드에 대해 양과 늑대의 수를 카운트해주고 영역에 대한 방문이 끝나면 양과 늑대 수를 리턴해준다.

다시 메인함수에서 영역에 대한 양과 늑대 수를 받아 조건에 맞게 계산한다.

코드

package BOJ.bfs;

import java.util.*;
import java.io.*;
public class No3184_양 {
    static char[][] arr;
    static boolean[][] visited;
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};
    static int sheep=0;
    static int wolf=0;

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

        arr=new char[R][C];
        visited=new boolean[R][C];
        for(int i=0;i<R;i++){
            String str=br.readLine();
            for(int j=0;j<C;j++){
                char c=str.charAt(j);
                arr[i][j]=c;

                if(c=='o') sheep++;
                else if(c=='v') wolf++;
            }
        }

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                if(arr[i][j]!='#'&&!visited[i][j]){
                    int[] count=bfs(i,j);
                    if(count[0]>count[1]) wolf-=count[1];
                    else sheep-=count[0];
                }
            }
        }

        System.out.println(sheep+" "+wolf);
    }

    static int[] bfs(int x, int y){
        int v=0;
        int o=0;

        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(x,y));
        visited[x][y]=true;

        while(!q.isEmpty()){
            Node cur=q.poll();
            int px=cur.x;
            int py=cur.y;

            if(arr[px][py]=='o') o++;
            else if(arr[px][py]=='v') v++;

            for(int i=0;i<4;i++){
                int nx=px+dx[i];
                int ny=py+dy[i];

                if(nx<0||nx>=R||ny<0||ny>=C||visited[nx][ny]) continue;

                if(arr[nx][ny]!='#'){
                    q.offer(new Node(nx,ny));
                    visited[nx][ny]=true;
                }
            }
        }

        return new int[]{o,v};
    }

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