[백준/c++] 3184번: 양

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

3184번: 양

 

문제 요약

 

.  빈 필드 / # 울타리 / o 양 / v 늑대

 

한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면 두 칸은 같은 영역 안에 속해있다고 한다.

마당에서 탈출할 수 있는 칸(마당 밖으로 나갈 수 있는 칸)은 어떤 영역에도 속하지 않는다.

 

IF            영역 안의 양의 수 > 늑대의 수 → 늑대를 내쫓는다.

ELSE      늑대가 모든 양을 먹는다.

 

아침이 되었을 때, 살아남은 양과 늑대의 수를 출력하라.

 

 

범위

 

행 R과 열 C (3 ≤ R, C ≤ 250)

 

 

---

 

#가 아닌 경우, DFS를 시작한다.

마당에서 탈출할 수 있는 칸은 어떤 영역에도 속하지 않는다 → 가장자리는 취급하지 않는다.

 

 

• 가장자리는 취급하지 않는다.

이 문제에서 가장자리란, x = 0 || x = R-1 || y = 0 || y = C-1 인 경우를 의미하는데 이를 위해 반복문을 이 범위 내로 돌리면 된다.

 

 

• # 가 아닌 경우 (. / v / o 인 경우) && 방문한 곳이 아닌 경우

상하좌우 이동만 가능하므로 방향 배열을 아래와 같이 선언해주고,

int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

dfs를 호출할 때마다, 해당 위치에서 상하좌우로 이동하면서 dfs를 재귀 호출한다.

여기서 더 깊이 들어가지 않는 경우가 있는데

• 방문한 곳
• #(울타리) 이므로 이동 불가
• 이동할 수 있는 범위를 벗어난 경우

 

• 양의 수, 늑대 수 카운팅

하나의 영역 내 모든 곳을 방문하면서 양(o)의 수와 늑대(v)의 수를 카운팅 한다. 모두 방문했다면 dfs 탐색을 끝내고, 카운팅 된 개수를 비교해서 만약 양의 수(s_cnt)가 더 많으면 최종 살아있는 양의 수 카운트 변수(total_s)에 더해준다. 더 많지 않으면 최종 살아있는 늑대 수 카운트 변수(total_w)에 늑대의 수(w_cnt)를 더해준다.

 

 

#include <iostream>
using namespace std;
int R, C, s_cnt, w_cnt, total_s=0, total_w=0;
char yard[251][251];
bool visited[251][251];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void input(){
    cin >> R >> C;
    for(int i=0; i<R; i++) for(int j=0; j<C; j++) cin >> yard[i][j];
}

void dfs(int x, int y){
    visited[x][y] = true;
    if(yard[x][y] == 'o') s_cnt++;
    else if(yard[x][y] == 'v') w_cnt++;
    for(int i=0; i<4; i++){
        int dx = x + dir[i][0];
        int dy = y + dir[i][1];
        if(visited[dx][dy]) continue;       //방문한 곳
        if(yard[dx][dy] == '#') continue;   //'#'울타리로 이동 불가
        if(dx < 1 || dy < 1 || dx > R-2 || dy > C-2) continue; //범위 바깥
        dfs(dx, dy);
    }
}

void solution(){
    for(int x=1; x<R-1; x++){
        for(int y=1; y<C-1; y++){
            if(!visited[x][y] && yard[x][y] != '#'){
                s_cnt = w_cnt = 0; //초기화(dfs 들어가기전에)
                dfs(x, y);
                s_cnt > w_cnt ? total_s += s_cnt: total_w += w_cnt; //전체 카운팅 업뎃
            }
        }
    }
    cout << total_s << ' ' << total_w << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

재미있는 문제였다➿

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!