3187 양치기 꿍

으음 이거 딱 보자마자 DFS 문제인데..

 

가로 세로 최대값이 250이므로 최대 62500의 노드가 있을 것이다.

 

DFS의 시간복잡도는 O(V + E)이므로 125000번 확인한다.

 

시간 내에 잘 돌아갈 것 같고..

 

아 그런데 이 문제는 간선이 안 주어진다?? 그냥 점을 노드로 보고 풀어야 한다.

 

뭔가 기억 날랑말랑했는데 풀었던 문제였다. 

 

https://burningjeong.tistory.com/223

[코드포스 Practice18] E. Lakes in Berland

 

 

위 문제랑 비슷하게 풀었다.

 

비슷한 문제 나오니 좋군 ^____^ 

 

재밌게 풀었다. 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool visited[255][255];
char maps[255][255];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

int n, m;

void dfs(int x, int y, ii &res)
{
    if (visited[x][y] || maps[x][y] == '#')
        return ;

    visited[x][y] = true;
    if (maps[x][y] == 'v')
        res.yy++;
    else if (maps[x][y] == 'k')
        res.xx++;
    
    for (int i = 0; i < 4; i++)
    {
        if (x + dx[i] >= 0 && y + dy[i] >= 0 && y + dy[i] < m && x + dx[i] < n)
            dfs(x + dx[i], y + dy[i], res);
    }

}

int     main()
{
    scanf("%d %d", &n, &m);

    char tmp;
    scanf("%c", &tmp);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            scanf("%c", &maps[i][j]);
        scanf("%c", &tmp);
    }

    ii ans;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!visited[i][j] && maps[i][j] != '#')
            {
                ii res;
                res.xx = 0, res.yy = 0;
                dfs(i, j, res);
                
                if (res.xx > res.yy)
                    ans.xx += res.xx;
                else
                    ans.yy += res.yy;
            }
        }
    }

    printf("%d %d\n", ans.xx, ans.yy);

    return 0;
}