백준 3109번 빵집

문제 링크입니다: https://www.acmicpc.net/problem/3109

그리디하게 접근하는 DFS(Depth First Search) 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 파이프라인을 많이 만들기 위해서는 해당 파이프라인이 최대한 원웅이의 빵집 상단에 도달해야합니다.

2. 따라서, DFS 탐색을 오른쪽 상단, 오른쪽, 오른쪽 하단 순으로 탐색합니다.

3. 각 높이마다 시작해서 파이프라인을 생성할 수 있는지 확인하고 생성할 수 있으면 결과값에 더해줍니다.

#include <iostream>

#include <string>

#include <queue>

using namespace std;

 

const int MAX = 10000;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[3] = { { -1, 1 }, {0, 1}, {1, 1} };

 

int R, C;

string graph[MAX];

bool visited[MAX][500];

bool DFS(int y, int x)

{

        visited[y][x] = true;

        if (x == C - 1)

                 return true;

 

        for (int i = 0; i < 3; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if(0<=nextY && nextY < R && 0<=nextX && nextX < C)

                         if (!visited[nextY][nextX] && graph[nextY][nextX] == '.')

                         {

                                 bool flag = DFS(nextY, nextX);

                                 if (flag)

                                          return flag;

                         }

        }

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> R >> C;

 

        for (int i = 0; i < R; i++)

                 cin >> graph[i];

 

        int result = 0;

        for (int i = 0; i < R; i++)

                 result += DFS(i, 0);

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~