[BOJ] 3109 빵집 - JAVA

1. 문제

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

3109번: 빵집

• 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.
• 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.
• 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있다.
• 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 
• 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

---

2. 풀이

• 각 행마다 파이프라인 설정하는 함수를 불러온다. 항상 열의 번호는 0번이다.
• 재귀 base : 열 번호가 끝까지 왔다면 경우의 수를 하나 추가하고 true를 반환한다.
• 재귀 recursive
  • 3가지 방향으로 탐색하면서 다음 열로 갈 수 있는지 확인한다.
  • 갈 수 있다면 다음 열을 파라미터로 넣어서 부른 재귀가 true를 반환하는 지 확인한다.
  • 만약 true라면 더 이상 탐색하지 않고 같이 true를 반환하며 함수 자체를 종료한다.
• 다음 열로 갈 수 있는지 탐색은 항상 위, 중간, 아래 순으로 한다. 위에서부터 아래로 채우면서 탐색하는 중이기 때문이다. 한 번 간 곳은 그 이후로 다시 탐색하지 않기 때문에 이 순서가 중요하다. 

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

public class BOJ_3109_빵집 {
    static int R, C;
    static char[][] map;
    static int result;
    static int[] dr = {-1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];

        for (int r = 0; r < R; r++) {
            String line = in.readLine();
            for (int c = 0; c < C; c++) {
                map[r][c] = line.charAt(c);
            }
        }

        for(int r=0;r<R;r++){
            setPipeline(r, 0);
        }

        System.out.println(result);
    }

    private static boolean setPipeline(int rowNo, int colNo) {
        if (colNo == C - 1) {
            ++result;
            return true;
        }

        for (int i = 0; i < 3; i++) {
            int nr = rowNo + dr[i];
            if (nr >= 0 && nr < R && map[nr][colNo + 1] == '.') {
                map[nr][colNo+1] = '-';
                if(setPipeline(nr, colNo + 1)) return true;
            }
        }

        return false;

    }

}

---

3. 결과