백준 3109 - 빵집(C++)

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

3109번: 빵집

DFS를 이용한 문제입니다.

첫번째 열이 다른 빵집, 마지막 열이 자신의 열일 때, 파이프라인을 최대 몇개까지 이을 수 있는지 구하는 문제입니다.

 

파이프 라인을 이을 수 있는 방법은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선인 총 3개입니다.

 

파이프라인을 최대로 짓는 수를 구하는 문제이기에, 첫째 열에서 모든 행의 값을 전부 DFS로 확인해봐야합니다.

X번째 행에서 시작한 파이프가 마지막 열에 도달할 수만 있으면 총 갯수를 하나씩 증가해줍니다.

 

마지막에 파이프 라인 갯수만 출력해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int N, M, cnt;
char map[10001][501];
int dy[3] = {1, 1, 1};
int dx[3] = {-1, 0, 1};
int Visit[10001][501];
bool check;

void dfs(int x, int y){
    Visit[x][y] = 1;
    if(y == M){
        cnt++;
        check = true;
        return;
    }
    for(int i = 0; i < 3; i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
            if(map[xx][yy] == '.' && Visit[xx][yy] != 1){ 
                dfs(xx, yy);
                if(check) return;
            }
        }
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        check = false;
        dfs(i, 1);
    }
    cout << cnt;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요