문제풀이/백준
[백준]3109: 빵집 - JAVA
빈둥벤둥
2021. 4. 17. 16:56
[백준]3109: 빵집

3109번: 빵집
유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던
www.acmicpc.net
풀이
첫 번째 열에서 마지막 열까지 도달할 수 있는 최대 경로를 반환하는 문제로 DFS를 사용하였다. '
DFS함수의 반환타입을 Boolean으로 설정하여 첫 번째 열에서 행의 위치를 변경하며 마지막 열까지 도달할 수 있다면 true, 아니면 false를 반환하도록 하였다. true를 반환했다면 도달 할 수 있다는 의미이므로 count++를 해주었다.
이때 파이프를 설치할 수 있는 위치는 현재 위치의 오른쪽 위, 오른쪽, 오른쪽 아래 방향밖에 없으므로 dx, dy를 다음과 같이 설정해 주었다.
dx = {-1, 0, 1}
dy = {1, 1, 1}
또한 다시 방문한 곳은 재 방문하면 안되므로 boolean 타입의 memo함수를 사용해 주었다.
코드
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
|
import java.util.*;
public class Main {
static int[] dx = {-1, 0, 1};
static int[] dy = {1, 1, 1};
static int r, c;
static char[][] board;
static boolean[][] memo;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
r = scan.nextInt();
c = scan.nextInt();
scan.nextLine();
board = new char[r][c];
for(int i = 0; i < r; i++) {
String str = scan.nextLine();
for(int j = 0; j < c; j++) {
board[i][j] = str.charAt(j);
}
}
memo = new boolean[r][c];
int count = 0;
for(int i = 0; i < r; i++) {
if(dfs(i, 0)) count++;
}
System.out.println(count);
}
public static boolean dfs(int x, int y) {
for(int i = 0; i < 3; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < r && ny < c) {
if(memo[nx][ny] == false && board[nx][ny] == '.') {
memo[nx][ny] = true;
if(ny == c - 1) return true;
if(dfs(nx, ny)) return true;
}
}
}
return false;
}
}
|
cs |