[ BOJ 백준 3109번 - 빵집 ] 해설 및 코드

https://www.acmicpc.net/problem/3109

3109번: 빵집

 

목적

건물('x')을 피해서 파이프를 겹치지 않게 놓을 수 있는 최대 개수를 구한다.

접근법

1. 파이프의 최대 개수는 R이하의 값으로, dfs 알고리즘으로 1행 1열~ 1행 R열까지 검사한다.

2. C행에 도달했다면 더이상 dfs로 탐색하지 않는다.

 

#include<iostream>
using namespace std;
 
int r, c, d[] = { -1,0,1 },cnt;
char b[10001][501];
bool found;
 
void find(int i,int j) {
    if (j == c-1) {
        found = true;
        ++cnt;
        return;
    }
    
    ++j;
    for (int k = 0; k < 3; ++k) {
        int ni = i + d[k];
        if (ni == -1 || ni == r || b[ni][j]=='x')continue;
 
        b[ni][j] = 'x';
        find(ni, j);
 
        if (found)return;
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> r >> c;
    for (int i = 0; i < r; ++i)cin >> b[i];
 
    cnt = 0;
    for (int i = 0; i < r; ++i) {
        found = false;
        find(i, 0);
    }
    cout << cnt;
}