[Baekjoon] #3184 양

[Baekjoon][https://www.acmicpc.net/problem/3184]

 

각 울타리 안에 있는 늑대와 양의 개수를 구하고 비교하는 문제로

너비 우선 탐색(BFS) 알고리즘 적용

 

미키의 뒷마당에서 울타리가 아니고(map[r][c] != ’#’) && 방문하지 않은(visit[r][c] != 0) 영역 일 때 BFS 알고리즘을 호출한다.

현재 위치를 Queue 값에 넣은 후 Queue 값이 존재 할 경우 상, 하, 좌, 우 방향으로 이동하면서

울타리 안에 있는 영역의 늑대와, 양의 수를 구한다.

 

수직, 수평으로 이동하면서 울타리 안 영역을 모두 BFS로 탐색 시,

늑대와 양의 수를 구한 후 늑대가 존재하면 전체 늑대 수에 남은 늑대 수를 더해주고,

양이 존재하면 전체 야 수에 남은 양 수를 더해준다.

 

이렇게 울타리 안 모든 영역을 BFS로 한 번씩 탐색 후 전체 개수를 출력한다.

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Location3184{
	int x;
	int y;
	
	public Location3184(int x, int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
}

// Queue에 들어갈 기준점이 필요

public class Main {

	static int r;
	static int c;
	static char map[][];
	static int visit[][];
	static Queue<Location3184> location;
	static int total_sheep =0;
	static int total_wolf = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		r = sc.nextInt();
		c = sc.nextInt();
		
		map = new char[r][c];
		visit = new int[r][c];
		location = new LinkedList<>();
		
		for(int i=0;i<r;i++) {
			String str = sc.next();
			for(int j=0;j<c;j++) {
				map[i][j] = str.charAt(j);
			}
		}
		

		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(map[i][j] != '#' && visit[i][j] == 0) {
					getBFS(i, j);
				}
			}
		}
		
		
		System.out.println(total_sheep+" "+total_wolf); 
	}
	
	public static void getBFS(int i, int j) {
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		int curSheep = 0;
		int curWolf = 0;
		visit[i][j] = 1;
		location.offer(new Location3184(i, j));
		
		if(map[i][j] == 'o') {
			curSheep++;
		} else if(map[i][j] == 'v') {
			curWolf++;
		}
		
		while(!location.isEmpty()) {
			int x = location.peek().x;
			int y = location.poll().y;

			for(int k=0;k<4;k++) {
				int ax = x+xx[k];
				int ay = y+yy[k];
				
				if(ax>=0 && ay>=0 && ax<r && ay<c) {
					if(visit[ax][ay] == 0 && map[ax][ay] == 'o') {
						curSheep++;
					} else if( visit[ax][ay] == 0 && map[ax][ay] == 'v') {
						curWolf++;
					}
					
					if(visit[ax][ay] == 0 && map[ax][ay] != '#') {
						location.offer(new Location3184(ax, ay));
						visit[ax][ay] = 1;
					}
				}
			}
		}

		if(curWolf>=curSheep) {
			total_wolf += curWolf;
		} else if(curSheep > curWolf) {
			total_sheep += curSheep;
		}
	}
}