[BaekJoon/백준] 3184번 양

 

이 문제는 DFS로 해결했다.

 

각 위치가 아직 방문되지 않았고, 울타리가 아닐 경우 DFS를 시작한다.

DFS 과정에서는 탐색을 하면서 w, o 갯수를 세고

DFS 한 사이클이 끝나면, 그동안 카운팅 했던 w, o 수를 비교하여 정산을 하면 된다.

// DFS 각각 하면서, VISIT 처리
// 방문 하면서 늑대 양 세고 끝나고 계산 처리.

#include <iostream>

using namespace std;


int R, C; // Row - Column
char FILED[251][251]; // NULL char 예방
bool VISIT[251][251]; // NULL char 예방

// 양, 늑대 수 (계산용)
int Sh_C, Wo_C;


// 양, 늑대 수 (결과용)
int TSh_C, TWo_C;

// 상 하 좌 우
int sx[4] = {-1, 1, 0, 0};
int sy[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
        
    VISIT[x][y] = true; // 방문
    
    if(FILED[x][y] == 'v')
        Wo_C++; // 늑대 증가
    else if(FILED[x][y] == 'o')
        Sh_C++; // 양 증가
    
    
    int xx, yy;

    
    for(int i = 0; i < 4; i++) {
        
        xx = x + sx[i];
        yy = y + sy[i];
        
        if(xx < 0 || xx > R || yy < 0 || yy > C)
            continue;
        
        if(!VISIT[xx][yy] && FILED[xx][yy] != '#') { // 방문 안했으며, 울타리가 아닐 경우에만
            dfs(xx, yy);
        }
    }
    
    
    
    
    
}

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    
    cin >> R >> C;
    
    
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            cin >> FILED[i][j];
        }
    }
    
    
    
    for(int i = 0; i < R; i++) {
        for(int j = 0; j < C; j++) {
            
            if(!VISIT[i][j] && FILED[i][j] != '#') { // 방문안했으며, 울타리가 아닐 경우에만 시작.
                
                // 초기화
                Wo_C = Sh_C = 0;
                                
                dfs(i, j);
                
                // 탐색 마쳤으면 정산.
                if(Sh_C <= Wo_C)
                    TWo_C += Wo_C;
                else
                    TSh_C += Sh_C;
                
            }
            
        }
    }
    
    cout << TSh_C << " " <<  TWo_C << "\n";
    
    
    
    
}

/*
6 6
...#..
.##v#.
#v.#.#
#.o#.#
.###.#
...###
*/