[알고리즘 문제] 백준3109 - 빵집

www.acmicpc.net/problem/3109

3109번: 빵집

dfs로 문제를 풀 수 있으며 왼쪽 시작점을 1행 ~ R-1까지 시작점을 바꾸어 가면서 각 시작점에서 출발하여 오른쪽 끝에 도착할 수 있다면 +1을 해줍니다. 여기서 무조건 방문할 때마다 visited[y][x]=1을 해주는데, 이는 y,x위치에서 파이프를 연결할 수 있는지, 없는지 모르지만 어쨋든 방문했다를 표시하기 위함입니다. 다른 시작위치에서 y,x를 간다고 하여도 이미 y,x를 거쳐가는 경우 파이프를 연결할 수 있는지/없는지 정해졌고 결과값에 더해졌기 때문입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int visited[10001][501] = {0};
char arr[10001][501];
int height, width;

int dx[3] = {1, 1, 1}; // 우상,우,우하
int dy[3] = {-1, 0, 1};

int ans = 0;

int search(int x, int y)
{
    queue<pair<int, int>> que;

    que.push({x, y});

    while (!que.empty())
    {
        pair<int, int> cur = que.front();
        que.pop();
        visited[cur.second][cur.first] = 1;

        if (cur.first == width - 1)
        {
            return 1;
        }

        for (int i = 0; i < 3; i++)
        {
            int newX = cur.first + dx[i];
            int newY = cur.second + dy[i];

            if (newX < 0 || newY < 0 || newX >= width || newY >= height)
            {
                continue;
            }
            if (!visited[newY][newX] && arr[newY][newX] == '.')
            {
                que.push({newX, newY});
                break;
            }
        }
    }
    return 0;
}

int main()
{
    cin >> height >> width;
    for (int y = 0; y < height; y++)
    {
        string s;
        cin >> s;
        for (int x = 0; x < s.size(); x++)
        {
            arr[y][x] = s[x];
        }
    }

    int ans = 0;
    for (int y = 0; y < height; y++)
    {
        ans += search(0, y);
    }

    cout << ans << endl;

    return 0;
}