[BOJ] 백준 [3109] 빵집 JAVA

https://www.acmicpc.net/problem/3109

3109번: 빵집

[문제]

[풀이]

왼쪽에서 오른쪽으로 파이프를 쭉 연결해야 하는데 , 최대한 많이 연결해야 한다.
그러기위해선 2가지의 조건을 생각해야한다.

1. [오른쪽위 , 오른쪽, 오른쪽아래] 순서대로 연결해야함
 => 만약 y좌표가 0번째에서 출발해서 맨 오른쪽 아래에 꽂히면 다른 1~n 번째에서는 절대 연결이 불가능

2. 이 문제는 백트래킹문제가 아니라 그리디 문제이기 때문에 모든 경우를 따지면 안된다
 => 종결조건에 다다르면 그 즉시 return 하여 이전에 호출된 재귀탐색을 종료시켜야 함

이 조건대로 그리디+DFS 풀어내면 연결된 총 파이프라인 수를 구할 수 있다

import java.util.*;
import java.io.*;
import java.util.stream.*;

import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;
import static java.util.stream.IntStream.*;

public class Main {
    static final int[] dx={1,1,1},dy={-1,0,1};
    static int w,h,result=0;
    static char[][] map;
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 초기 설정
        h = input[0]; w = input[1];
        map = new char[h][w];
        visit = new boolean[h][w];
        for(int i=0;i<h;i++) map[i] = br.readLine().toCharArray();

        // 첫줄 차례대로 탐색
        for(int i=0;i<h;i++)
            dfs(0, i);

        System.out.println(result);
    }

    static boolean dfs(int curX,int curY){

        // 종결조건
        if(curX==w-1){
            result++;
            return true;
        }

        for(int i=0;i<dx.length;i++){

            int nextX = curX+dx[i];
            int nextY = curY+dy[i];

            if(!isRange(nextX,nextY)) continue;
            visit[nextY][nextX] = true;

            // 백트래킹 방지
            if(dfs(nextX,nextY)) return true;
        }
        return false;
    }

    static boolean isRange(int x,int y){
        return x>=0&&y>=0&&x<w&&y<h&&!visit[y][x]&&map[y][x]=='.';
    }
}