[ 백준 3109 ] 빵집 (C++)

백준의 빵집(3109) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 첫 번째 열에서 갈 수 있는 오른쪽 칸으로 한 칸씩 전진해보면서 가장 마지막열까지 갈 수 있는지 판단해야

   하는 문제이다.

   본인은 현재 파이프를 만들고자 하는 칸에 다른 파이프가 놓여져 있는지 아닌지를 판단하기 위해서 Visit[][] 2차원 배열을

   사용하였다.

   가장 왼쪽열에 있는 모든 행을 시작점으로 잡으며, 가장 오른쪽열까지 갈 수 있을 때마다 정답갯수를 ++ 해주면서

   전체 연결 가능한 파이프의 갯수를 Count해주면 된다.

   문제 자체는 그리 어렵지 않으니 소스코드를 보면 쉽게 이해할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 10000
using namespace std;
 
int R, C, Answer;
char MAP[MAX][500];
bool Visit[MAX][500];
bool Ans;
 
int dx[] = { -1, 0, 1 };
int dy[] = { 1, 1, 1, };
void Input()
{
    cin >> R >> C;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void DFS(int x, int y)
{
    Visit[x][y] = true;
    if (y == C - 1)
    {
        Ans = true;
        Answer++;
        return;
    }
 
    for (int i = 0; i < 3; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx >= 0 && ny >= 0 && nx < R && ny < C)
        {
            if (MAP[nx][ny] == '.' && Visit[nx][ny] == false)
            {
                DFS(nx, ny);
                if (Ans == true) return;
            }
        }
    }
}
 
void Solution()
{
    for (int i = 0; i < R; i++)
    {
        Ans = false;
        DFS(i, 0);
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}