[ 백준 ][ 3184 ][ 양 ]

백준 3184 양 문제

오래간만에 다시 알고리즘 문제를 잡는다.

너무 바빠서 손도 못댔다가 하루하루 하면서 다시 감을 익혀 보려고 한다. 

감잡기용으로 전에 푼거말고 새로운 문제를 풀어보고 싶었는데 (사실 다 기억이 안남)

간단해보이고 무엇보다도 정답률이 높아 선택했다

구역마다 양과 늑대의 수를 세서 조건에 맞춰

출력해주는 간단한 문제였다

답지를 안보고 기억을 끄집어내면서 풀었는데

얼추 기억은 나는 것 같다 

그나저나 아이패드 가지고 싶다...ㅎ

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

class glassPoint{
	int y;
	int x;
	glassPoint(int y, int x){
		this.y = y;
		this.x = x;
	}
}
public class Main_backjoon_3184_양 {
	static int N;
	static int M;
	static int WOLF;
	static int SHEEP;
	static int[] dx = {1, -1, 0,  0};
	static int[] dy = {0,  0, 1, -1};
	static char[][] map = new char[251][251];
	static boolean[][] visited = new boolean[251][251];
	static Queue q = new LinkedList();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()) {
                String s = st.nextToken();
                for(int j = 0 ; j < M; j++) {
                    //System.out.print(s.charAt(j));
                	visited[i][j] = false;
                    map[i][j] = s.charAt(j);
                }
            }
		}
		
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] != '#' && visited[i][j] == false) {
					bfs(i,j);
				}
			}
		}
		System.out.println(SHEEP + " " + WOLF);
	}
	public static void printVisted() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(visited[i][j] == true ) {
					System.out.print('1');
				}
				else {
					System.out.print('0');
				}
			}
			System.out.println();
		}
	}
	public static void bfs(int y, int x) {
		int wolf = 0;
		int sheep = 0;
		q.add(new glassPoint(y,x));
		if(map[y][x] == 'v') { wolf += 1;}
		if(map[y][x] == 'o') { sheep += 1;}
		visited[y][x] = true;
		
	
		while(!q.isEmpty()) {
			glassPoint g = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int yy = dy[i] + g.y;
				int xx = dx[i] + g.x;
				if(yy >= 0 && yy < N & xx >= 0 && xx < M) {
					//방문도 안하고 벽이 아닌경우 
					if(visited[yy][xx] == false && map[yy][xx] != '#') {
						q.add(new glassPoint(yy,xx));
						visited[yy][xx] = true;
						//printVisted();
						//늑대 인경우 
						if(map[yy][xx] == 'v') {
						
							wolf++;
						}
						//양인경우 
						else if(map[yy][xx] =='o') {
						
							sheep++;
						}
					}
				}
			}
		}
		
		//양 다 잡아 먹힘 
		if( wolf >= sheep) { 
			WOLF += wolf;
		
		}else { //양이 이김 
			SHEEP += sheep;
		}
	}

}