https://www.acmicpc.net/problem/3109
3109번: 빵집
문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵
www.acmicpc.net
목적
건물('x')을 피해서 파이프를 겹치지 않게 놓을 수 있는 최대 개수를 구한다.
접근법
1. 파이프의 최대 개수는 R이하의 값으로, dfs 알고리즘으로 1행 1열~ 1행 R열까지 검사한다.
2. C행에 도달했다면 더이상 dfs로 탐색하지 않는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#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;
}
|
'Problem Solving > BOJ 백준' 카테고리의 다른 글
[ BOJ 백준 2823 번 - 유턴 싫어 ] 해설 및 코드 (0) | 2019.12.09 |
---|---|
[ BOJ 백준 2629번 - 양팔저울 ] 해설 및 코드 (0) | 2019.12.09 |
[ BOJ 백준 2339번 - 석판 자르기 ] 해설 및 코드 (0) | 2019.12.08 |
[ BOJ 백준 11729번 - 하노이 탑 이동 순서 ] 해설 및 코드 (0) | 2019.12.08 |
[ BOJ 백준 1405번 - 미친 로봇 ] 해설 및 코드 (0) | 2019.12.08 |