백준 3109 빵집 (greedy, dfs)

문제 : 3109번: 빵집 (acmicpc.net)

3109번: 빵집

 

풀이과정

첫 번째 열 -> 마지막 열 까지 파이프를 겹치지 않게 연결하면서 구할 수 있는 최대 파이프 수를 구하는 문제입니다.

 

건물이 있는 곳은 1, 지나갈 수 있는 곳은 0으로 채워줬으며, visited 배열을 사용해서 한번 방문한 곳은 다시 방문하지 않도록 했습니다.

 

탐색하는 순서를 오른쪽 위, 오른쪽, 오른쪽 아래 순서대로 탐색하기 때문에 greedy 알고리즘이 적용됩니다

#include <iostream>
#include <set>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int R,C;
int A[10001][501];
int visited[10001][501];
// 무조건 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색해서
// greedy하게 답을 찾아야한다
int dy[3] = {-1,0,1};
int dx[3] = {1,1,1};
int flag = false;
int answer = 0;

void solution(int y, int x) {
    visited[y][x] = 1;
    if(x == C-1) {
        flag = true;
        answer++;
        return;
    }

    for(int i=0; i<3; i++) {
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(ny >= R || ny < 0) continue;
        if(visited[ny][nx] || A[ny][nx] == 1) continue;

        solution(ny,nx);
        if(flag) return;
    }
}

int main()
{
    string s;
    scanf("%d %d",&R,&C);
    for(int i=0; i<R; i++) {
        cin >> s;
        for(int j=0; j<s.size(); j++) {
            if(s[j] == '.') A[i][j] = 0;
            else A[i][j] = 1;
        }
    }
    for(int i=0; i<R; i++) {
        flag = false;
        solution(i,0);
    }
    printf("%d\n",answer);
}