[1388번] 바닥 장식

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

이 문제 분류가 파싱으로 되어있지만, 파싱또한 구현이라는 의미에서는 같은 의미라 볼 수 있다.

-와 |가 어떻게 나타나는지 알아야 하는데, 단순한 dfs로 문제를 해결 할 수 있다.

가로인 경우 가로일 때 까지 계속 파악해줘서 1(true)을 더해주면 되고,

세로인 경우도 마찬가지로 해주어 모든 string을 검사하면 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
bool visit[102][102];
string str[101];
 
bool garo(int i, int j)
{
    if (visit[i][j])
        return false;
 
    visit[i][j] = true;
 
    if (str[i][j + 1] == '-')
        garo(i, j + 1);
 
    return true;
}
 
bool sero(int i, int j)
{
    if (visit[i][j])
        return false;
 
    visit[i][j] = true;
 
    if (str[i + 1][j] == '|')
        sero(i + 1, j);
 
    return true;
}
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        cin >> str[i];
 
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (str[i][j] == '-')
                cnt += garo(i, j);
            else
                cnt += sero(i, j);
    }
 
    cout << cnt;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>