BOJ 3187 양치기 꿍

링크

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

3187번: 양치기 꿍

풀이

구역별로 BFS를 돌리며 카운팅을 해줌!

코드

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

int r, c, r_v_c, r_k_c, t_v_c, t_k_c;
int xl[] = {0,0,-1,1};
int yl[] = {1,-1,0,0};
char map[250][250], visit[250][250];
queue < pair<int, int> > q;

int check(int x, int y){
	if(0<=x&&x<r&&0<=y&&y<c)
		return 1;
	return 0;
}

int main() {
	//freopen("input.txt","r",stdin);
	
	cin>>r>>c;
	getchar();
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			scanf("%c",&map[i][j]);
		}
		getchar();
	}
			
			
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			if(map[i][j]!='#'&&!visit[i][j]){
				t_v_c=t_k_c=0;
				q.push({i,j});
				visit[i][j] = 1;
				while(!q.empty()){
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					
					if(map[x][y]=='v')
						t_v_c++;
					if(map[x][y]=='k')
						t_k_c++;
					
					for(int ii=0;ii<4;ii++){
						int nx = x+xl[ii];
						int ny = y+yl[ii];
						if(check(nx,ny)&&map[nx][ny]!='#'&&!visit[nx][ny]){
							visit[nx][ny]=1;
							q.push({nx,ny});
						}
					}
				}
				if(t_v_c<t_k_c){
					r_k_c+=t_k_c;
				}
				else{
					r_v_c+=t_v_c;
				}
			}
		}
	}
	cout<<r_k_c<<" "<<r_v_c;
}