3184번 양

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

난이도는 매우 쉬웠다.

문제 유형은 BFS로 되어있길래

BFS보다는 DFS가 더 시간 줄일 수 있을 것 같아서

DFS로 풀었다.

처음에 60번 째 줄을 if(!visit[i][j] && Map[i][j] == '.') 라고 작성했었는데

바로 생각해보니 

3 3

.#o

.#v

.##

라는 반례가 있었다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
char Map[255][255];
 
int R = 0, C = 0, v = 0, o = 0, tv = 0, to = 0;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
bool visit[255][255] = { false, };
 
void DFS(int r, int c)
{
    if (Map[r][c] == 'o') ++o;
    else if (Map[r][c] == 'v') ++v;
 
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i], x = c + dx[i];
 
        if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || Map[y][x] == '#') continue;
 
        DFS(y, x);
    }
}
 
int main(void)
{
    scanf("%d %d", &R, &C);
 
    for (int i = 0; i < R; i++)
    {
        scanf("%s", Map[i]);
 
        for (int j = 0; j < C; j++)
            if (Map[i][j] == 'o') ++to;
            else if (Map[i][j] == 'v') ++tv;
    }
 
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (!visit[i][j] && (Map[i][j] == 'o' || Map[i][j] == 'v'))
            {
                o = v = 0;
 
                DFS(i, j);
 
                if (o <= v) to -= o;
                else tv -= v;
            }
    
    printf("%d %d\n", to, tv);
    
    return 0;
}