3109번: 빵집
유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던
www.acmicpc.net
파이프는 오른쪽, 대각선 오른쪽 위, 대각선 오른쪽 아래 방향으로 연결할 수 있고,
0번 열에서 M - 1번 열까지 파이프를 이어야하며 최종적으로 파이프라인의 최대 갯수를 출력하는 문제입니다.
저는 여기서 앞의 열에서 최대한 앞쪽의 열에 파이프를 연결하면 될것이라는 생각을 하여 백트래킹에 그리디알고리즘을 사용하였습니다.
(0, 0) ~ (N - 1, 0)까지 각각 dfs로 끝 열에 도달할 수 있는지 확인해줍니다.
그리디를 사용했기때문에 오른쪽 위 -> 오른쪽 -> 오른쪽 아래 방향 순으로 탐색해줍니다.
끝 열에 도달하면 true를 리턴해주고, 도달하지 못하면 false를 리턴합니다.
true일 경우에만 ans++를 하여 최종 답을 출력합니다.
visit배열을 초기화하지 않은 이유는
파이프는 겹칠수 없어서 앞쪽에서 연결한 파이프와 겹칠 수 있기 때문입니다.
만약 최종적으로 연결한 파이프가 아니라고 해도 그 위치에서는 파이프를 연결할 수 없다는 뜻이 되므로 초기화를 하지 않아야합니다.
[C++]
|
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
51
52
53
|
#include <iostream>
using namespace std;
bool visit[10010][510];
char list[10010][510];
int direct[3][2] = { {-1,1},{0,1},{1,1} };
int N, M, ans;
bool dfs(int x, int y) {
visit[x][y] = true;
if (y == M - 1) return true;
for (int i = 0; i < 3; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (visit[nx][ny] || list[nx][ny] == 'x') continue;
bool chk = dfs(nx, ny);
if (chk)
return true;
}
return false;
}
void func() {
for (int i = 0; i < N; i++) {
if (dfs(i, 0)) ans++;
}
cout << ans << '\n';
}
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> list[i][j];
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[Java]
|
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
51
52
53
54
55
56
57
58
59
60
61
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int direct[][] = { { -1, 1 }, { 0, 1 }, { 1, 1 } };
static boolean visit[][];
static char list[][];
static int N, M, ans;
static boolean dfs(int x, int y) {
visit[x][y] = true;
if (y == M - 1)
return true;
for (int i = 0; i < 3; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (visit[nx][ny] || list[nx][ny] == 'x')
continue;
boolean chk = dfs(nx, ny);
if (chk)
return true;
}
return false;
}
static void func() {
for (int i = 0; i < N; i++) {
if (dfs(i, 0))
ans++;
}
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new char[N][];
visit = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 16922 로마 숫자 만들기 (0) | 2021.02.24 |
|---|---|
| boj 1987 알파벳 (0) | 2021.02.18 |
| boj 17406 배열 돌리기 4 (0) | 2021.02.10 |
| boj 16927 배열 돌리기 2 (0) | 2021.02.10 |
| boj 16926 배열 돌리기 1 (0) | 2021.02.10 |