[백준 3184] 양

양

문제설명

행과 열을 입력 받은 다음, #은 울타리 .은 아무것도 없음, o는 양 그리고 v는 늑대를 의미한다.

이때 울타리 공간 안에 양의 수가 늑대의 수보다 많으면 양은 늑대를 밀어 낼 수 있다.

다른 말로는 늑대가 양의 수보다 많거나 같으면 늑대가 양을 처리한다.
따라서 다음 날의 존재하는 늑대와 양의 수를 출력시킨다.

알고리즘

1. 문자열과 행과 열의 값을 입력 받는다.
2. 각 값을 조회하는데, 그 칸을 방문 하지않았고, 울타리가 아닌 경우 DFS 함수로 조회한다.
3. DFS 함수에서는 방문 표시를 하고 늑대, 양의 수를 세며, 울타리는 종료시킨다.
4. 늑대나 양을 센 경우에는 그 구역 내의 다른 칸도 확인하기 위해서 상하좌우로 이동하며 다른 양이나 늑대의 수를 센다.
5. DFS 함수에서 빠져나와서 해당 구역에 늑대와 양의 수의 판별을 통해 살아있는 늑대나 양의 수를 구한다.
6. 모든 구역을 보고 난 후 전체 양과 늑대의 수를 출력 시킨다.

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAX 251

char graph[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int ans = 0;
int r, c;
int cnt1, cnt2;//cnt1=양의 수, cnt2=늑대의 수 
int ans1, ans2;//ans1=양의 총 수, ans2=늑대의 총 수 

void dfs(int x, int y)
{
    visited[x][y] = true;//새로운 곳 방문 표시
    if (graph[x][y] == 'o')//양 수 세기
        cnt1++;
    if (graph[x][y] == 'v')//늑대 수 세기
        cnt2++;
    if (graph[x][y] == '#')//울타리면 막혔으니 종료
        return; 

    for (int i = 0; i < 4; i++)
    {    
        int move_x = x + dx[i];
        int move_y = y + dy[i];

        if (move_x >= 0 && move_x < r && move_y >= 0 && move_y < c)//범위 안에 포함되면 이동 가능
        {
            if(!visited[move_x][move_y])//방문 한 적 없으면 방문 가능            
                dfs(move_x, move_y);
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> r >> c; //가로 세로 입력

    for (int i = 0; i < r; i++)//장소 상태 입력 
    {
        for (int j = 0; j < c; j++)
            cin >> graph[i][j];
    }

    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            if (graph[i][j] != '#' && visited[i][j]==false)//울타리가 아니고 방문한적 없으면 조회
            {
                dfs(i, j);//조회
                if (cnt1 > cnt2)//양이 늑대보다 많으면
                    ans1 += cnt1;//양이 이김
                else//늑대가 더 많거나 같으면 
                    ans2 += cnt2;//늑대가 이김

            }
            //다른 구역이므로 양과 늑대 수 초기화
            cnt1 = 0;
            cnt2 = 0;
        }
    }

    cout << ans1 << " " << ans2 << "\n";//결과 값 출력
    return 0;
}

고찰

이번 문제는 dfs 알고리즘을 활용하여 풀 수 있었던 문제였다.
각 구역을 나누는게 중요한 문제였기 때문에 울타리를 의미하는 '#'을 만났을 때만 잘 고려하면 풀 수 있는 문제였다.
따라서 울타리를 만났을 때는 뛰어 넘거나 DFS 함수도 종료시키면 수월하게 풀 수 있는 문제였다.