3109번: 빵집 
문제 링크: 3109번: 빵집
개요
n*m 크기의 맵이 주어지면 왼쪽부터 오른쪽까지 연결하는 파이프라인을 겹치지 않게 설치할 수 있는 최대 개수를 구하는 문제이다. 최대한 많은 파이프라인을 만들어야 하기 때문에 왼쪽 가장 위 칸에서부터 시작하며, 오른쪽으로 파이프를 연결할 때는 위, 중간, 아래 순으로 진행한다.
풀이
main 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
scanf("%d %d", &n, &m); getchar();
for (int i = 0; i < n; i++) {
scanf("%s", map[i]); getchar();
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += dfs(i, 0);
}
printf("%d", ans);
return 0;
}
ans는 출력할 파이프라인의 수로, for문을 돌며 값을 누적해 나갈 것이다. dfs(n, m)은 (n, m) 위치에서 파이프를 연결해 오른쪽 끝에 도달할 수 있으면 1, 없으면 0을 반환한다. 가장 왼쪽 칸을 위에서부터 순서대로 탐색하며, 현재 상태에서 오른쪽 끝까지 도달할 수 있는지 여부를 dfs 함수를 이용해 확인하고 그 값을 ans에 누적하여 출력한다.
dfs 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dfs(int x0, int y0) {
vstd[x0][y0] = 1;
if (y0 == m - 1) return 1;
for (int d = 0; d < 3; d++) {
int x = x0 + dx[d];
int y = y0 + 1;
if (0 <= x && x < n && 0 <= y && y < m) {
if (!vstd[x][y] && map[x][y] == '.') {
if (dfs(x, y) == 1) return 1;
}
}
}
return 0;
}
이미 방문한(파이프가 놓여있는) 곳에 또 파이프를 놓지 않기 위해 vstd 배열을 이용했다. 현재 위치에서 오른쪽 위, 중간, 아래 순으로 탐색을 진행하며, 더 이상 오른쪽으로 갈 수 없으면 0을, 가장 오른쪽 칸에 도달하면 1을 반환한다.
전체 코드
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
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_N 10000
#define MAX_M 500
int n, m;
char map[MAX_N][MAX_M+1], vstd[MAX_N][MAX_M] = { 0 };
const int dx[3] = { -1, 0, 1 };
int dfs(int x0, int y0);
int main() {
scanf("%d %d", &n, &m); getchar();
for (int i = 0; i < n; i++) {
scanf("%s", map[i]); getchar();
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += dfs(i, 0);
}
printf("%d", ans);
return 0;
}
int dfs(int x0, int y0) {
vstd[x0][y0] = 1;
if (y0 == m - 1) return 1;
for (int d = 0; d < 3; d++) {
int x = x0 + dx[d];
int y = y0 + 1;
if (0 <= x && x < n && 0 <= y && y < m) {
if (!vstd[x][y] && map[x][y] == '.') {
if (dfs(x, y) == 1) return 1;
}
}
}
return 0;
}