백준 3184 - 양 - DFS

문제

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

풀이전략

1. 양은 수평, 수직으로만 판단한다.
2. 어차피 모든 영역은 울타리로 둘러쌓여 있으니 한 영역당 양과 늑대의 개수를 새면된다.
3. R, C <=250이므로 DFS로 확인하여도 시간은 충분하다.

코드

#include<bits/stdc++.h>

using namespace std;

int R, C;
char a[252][252];
int wCnt =0, sCnt=0;
int wCntTotal =0, sCntTotal=0;
// 가로 세로 이동을 위한 배열
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void DFS(int r, int c){
    // 늑대, 양에 따라 수를 늘려준다.
    if(a[r][c] == 'v') wCnt++;
    else if(a[r][c] == 'o') sCnt++;
    // 이후 한번 지나간 영역은 울타리로 바꿔주어 중복체크를 피한다. 
    a[r][c] = '#';

    for(int i=0; i<4; i++){
        int rr = r+dy[i];
        int cc = c+dx[i];

        if(a[rr][cc] != '#'){
            DFS(rr,cc);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    memset(a, '#', sizeof(a));
    cin >> R >> C;
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            cin >> a[i][j];
        }
    }

    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            if(a[i][j] != '#'){
                DFS(i,j);
                if(wCnt >= sCnt) sCnt = 0;
                else if(wCnt < sCnt) wCnt = 0;
                wCntTotal += wCnt;
                sCntTotal += sCnt;
                wCnt = sCnt = 0;
            }
        }
    }
    cout<<sCntTotal << " "<< wCntTotal<<'\n';
    return 0;
}

소감

한 영역내에서 양의 수와, 늑대의 수만 파악하면 되는 문제이다. 이러한 문제를 기존 DFS코드에서 조금만 바꿔주면 된다.