백준 - 3109번(빵집)

문제 출처: https://www.acmicpc.net/problem/3109

문제

• 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.

• 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.

• 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.

• 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.

• 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.

• 원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.

• 원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static int[][] directions = {
            { -1, 1 }, // 오른쪽 위
            { 0, 1 },  // 오른쪽
            { 1, 1 },  // 오른쪽 아래
    };

    private static boolean result;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int R = Integer.parseInt(tokenizer.nextToken()); // 행
        int C = Integer.parseInt(tokenizer.nextToken()); // 열
        char[][] matrix = new char[R][C]; // 배열 생성
        for (int i = 0; i < R; i++) {
            matrix[i] = reader.readLine().toCharArray();
        }

        int ans = 0; // 파이프라인 갯수

        for (int i = 0; i < R; i++) {
            result = false; // 플래그 초기화
            recursive(matrix, i, 0, R, C);
            if (result) ans++; // 파이프라인이 완성된 경우 카운트 증가
        }

        System.out.println(ans);
    }

    // 백트래킹
    private static void recursive(char[][] matrix, int row, int col, int R, int C) {
        // 앞에서 가능한 수인지 체크를 하고 넘긴다.
        if (col == C - 1) {
            result = true;
            matrix[row][col] = 'x';
            return;
        }

        // 첫 열에서 시작
        matrix[row][col] = 'x';

        for (int j = 0; j < 3; j++) {
            int dy = row + directions[j][0];
            int dx = col + directions[j][1];

            if (dy >= 0 && dy < R && dx >= 0 && dx < C) {
                if (matrix[dy][dx] != 'x') recursive(matrix, dy, dx, R, C);
                if (result) break;
            }
        }
    }

}

• DFS를 활용한 문제였다. 가능한 길을 찾을 경우 이동하여 마지막 열까지 진행하고, 하나의 파이프라인을 완성하면 boolean flag를 통해 재귀를 멈추도록 하였다.
• 가능한 모든 경우의 수를 찾는 것이 아니라 파이프라인을 하나 완성시키면 종료해야 되는 부분이 놓치기 쉬울 것 같다.