문제 양

문제링크
실버 2
그래프 탐색

. 빈필드
'#' 울타리
o 양
v 늑대
상하좌우로 움직여서 울타리를 지나지않으면 같은영역
영역안의 양의 수가 늑대보다 많으면 양이 이김
아니면 늑대가 다 잡아 먹음

입력

행 R과 열 C
마당구조 R*C

출력

살아있는 양과 늑대 수

풀이

1. 벽이나 #(울타리)가 나올때까지 dfs 탐색 (find 함수)
2. 탐색하면서 양이나오면 o+1 해주고 늑대가 나오면 v+1 해준다.
3. 탐색이 끝나고 돌아와서 o와 v를 비교해서 살아남는 쪽만 전역변수인 V,O에 더해준다.
4. 위과정을 반복한 후 V,O를 출력해준다

코드

import java.util.Scanner;

public class 백준3184 {
	static int R,C,cnt,v=0,o=0,V=0,O=0;
	static Scanner scan =new Scanner(System.in);
	static int[] dx= {1,0,0,-1};
	static int[] dy= {0,-1,1,0};
	static boolean[][] visited;
	static char[][] arr;
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
			cnt=0;
			R=scan.nextInt();
			C=scan.nextInt();
			arr=new char[R+1][C+1];
			visited=new boolean[R+1][C+1];
		
			for(int i=0;i<R;i++) {
					String str=scan.next();
				for(int j=0;j<C;j++) {
					arr[i][j]=str.charAt(j);
				}
			}
			
			
			
			for(int m=0;m<R;m++) {
				for(int n=0;n<C;n++) {
					if((arr[m][n]=='v'||arr[m][n]=='o')&&!visited[m][n]) {
						v=0;o=0;
						find(m,n);
						if(o>v) {
							O+=o;
						}
						else V+=v;
					}
				}
		}
		System.out.print(O+" "+V);
	}
	static void find(int m,int n) {
		if(!visited[m][n]&&!(arr[m][n]=='#')) {//방문하지 않았고 울타리가 아니면
			visited[m][n]=true;
			if(arr[m][n]=='v') {
				v++;
			}else if(arr[m][n]=='o') {
				o++;
			}
			for(int i=0;i<4;i++) {
				int a=m+dx[i];
				int b=n+dy[i];
				if(a<R&&a>=0&&b<C&&b>=0) {
					if(!visited[a][b]) {
						find(a,b);
					}
				}
			}
		}
	}

}