백준 3184번 : 양

문제링크 :https://www.acmicpc.net/problem/3184

3184번: 양

 문제설명 

 

1. 울타리 ,늑대 ,양의 정보가 주어진다

2. 하루가 지나면 울타리내에 양의 숫자가 늑대보다 많을경우 늑대를 쫓아낼수있고 그외에는 양들이 잡아먹힌다.

3. 하루가 지난후 각울타리 내에 남아있는 양과 늑대의 숫자 총합을 출력 ,

 

 알고리즘 

 

1. DFS 알고리즘을 이용하여 각 컴포넌트 안에 늑대와 양의숫자를구함

2. 양의숫자가 많을 경우 양의 최종 숫자를 올려주고 개체수가 같거나 늑대의 숫자가 많을 경우 늑대의 숫자를 올려준다

3. 각 지점을 확인 한후 check를해주는 배열이 필요하다 .( 시간초과 방지 )

 

 코드 

 

#include<iostream>
 
 
using namespace std;
 
int R, C;
char map[255][255];
int visited[255][255];
 
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };
int sheep = 0, wolf = 0;
 
pair<int, int> result = make_pair(0, 0);
 
void dfs(int y, int x) {
    if (visited[y][x] == 1) return;
 
    visited[y][x] = 1;
 
 
    if (map[y][x] == 'v')wolf++;
    else if (map[y][x] == 'o')sheep++;
 
    for (int i = 0; i < 4; i++) {
        int next_x = x + dx[i];
        int next_y = y + dy[i];
 
        if (next_x >= 0 && next_x < R && next_y >= 0 && next_y < C) {
 
            if (map[next_y][next_x] == '#') continue;
            else {
                dfs(next_y, next_x);
            }
 
        }
    }
 
}
 
 
int main() {
    cin >> C >> R;
 
    for (int i = 0; i < C; i++) {
        for (int j = 0; j < R; j++) {
            cin >> map[i][j];
            visited[i][j] = 0;
        }
    }
    for (int i = 0; i < C; i++) {
        for (int j = 0; j < R; j++) {
            if (map[i][j] == '#')continue;
            
            if (visited[i][j] == 0) {
                sheep = 0;
                wolf = 0;
                //양,늑대가 울타리내에 있는 숫자를 구함
                dfs(i, j);
 
                //양이 더많으면 다음날 남아있는 양의 개체수 증가
                if (sheep > wolf) {
                    result = make_pair(result.first + sheep, result.second);
                }
                //그외에는 남아있는 늑대의 개체수 증가
                else {
                    result = make_pair(result.first, result.second + wolf);
                }
 
            }
        }
    }
 
    cout << result.first << " " << result.second;
}