문제풀이/백준

[백준]3109: 빵집 - JAVA

빈둥벤둥 2021. 4. 17. 16:56

[백준]3109: 빵집 

www.acmicpc.net/problem/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 = {-101};
    static int[] dy = {111};
    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 - 1return true;
                    if(dfs(nx, ny)) return true;
                }
            }
        }
        return false;
    }    
}
cs