[백준]3109: 빵집 - JAVA

[백준]3109: 빵집 

www.acmicpc.net/problem/3109

3109번: 빵집

풀이

첫 번째 열에서 마지막 열까지 도달할 수 있는 최대 경로를 반환하는 문제로 DFS를 사용하였다. '

 

DFS함수의 반환타입을  Boolean으로 설정하여 첫 번째 열에서 행의 위치를 변경하며 마지막 열까지 도달할 수 있다면 true, 아니면 false를 반환하도록 하였다. true를 반환했다면 도달 할 수 있다는 의미이므로 count++를 해주었다.

 

이때 파이프를 설치할 수 있는 위치는 현재 위치의 오른쪽 위, 오른쪽, 오른쪽 아래 방향밖에 없으므로 dx, dy를 다음과 같이 설정해 주었다.

dx = {-1, 0, 1}

dy = {1, 1, 1}

 

또한 다시 방문한 곳은 재 방문하면 안되므로 boolean 타입의 memo함수를 사용해 주었다. 

코드

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;
    }    
}