BOJ_3109 : 빵집

👉 문제링크

3109번: 빵집

---

---

🔸 문제 분석 🔸

• R x C 크기의 2차원 배열의 0번 열부터 C-1번 열까지 파이프를 연결하고자 한다.
• '.' 에는 파이프를 놓을 수 있고, 'x'에는 놓을 수 없다.
• 첫 열과 끝 열은  '.' 로만 채워져있다.
• 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래로만 연결할 수 있다.
• 놓을 수 있는 파이프의 최대값을 출력한다.

🔸 풀이 전략 🔸

• R이 최대 1만, C가 최대 500이므로 효율적인 선택 방법이 필요하다.(그리디)
• 최대한 많은 파이프를 두기 위해서는 가능한 위쪽으로 파이프를 연결한다.
• 0번 열의 0번 행부터 R-1번 행까지 순서대로 시작 위치로 삼는다.
• DFS와 백트래킹을 통해 파이프가 연결 가능한지 확인한다.
  • 한 좌표에서 우상, 우, 우하 순으로 탐색(재귀 메서드 호출) 한다.
  • 만약 파이프가 연결 됐다면, 재귀 메서드를 모두 중지해야 한다. (파이프가 두 갈래가 되지 않도록)
  • 파이프를 놓을 수 없더라도 체크해둔다. (중복으로 검사하지 않도록)
• 상태 공간 트리(state space tree) 형식이기도 하다.

🔸 코드 🔸

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

public class Main {
    private static int r, c;
    private static char[][] pipeline;
    private static int[] dx = {-1, 0, 1}; // 우상, 우, 우하
    private static int[] dy = {1, 1, 1}; // 우상, 우, 우하

    private static boolean pipe(int x, int y) {
//        print();
        if (y == c - 1) return true;

        for (int i = 0; i < 3; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < r && 0 <= ny && ny < c && pipeline[nx][ny] == '.') {
                pipeline[nx][ny] = 'X';
                if (pipe(nx, ny)) return true;
            }
        }
        return false;
    }

    private static void print() {
        System.out.println("=======================================");
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                System.out.print(pipeline[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        pipeline = new char[r][c];
        for (int i = 0; i < r; i++) {
            pipeline[i] = br.readLine().toCharArray();
        }

        // recursion
        int answer = 0;
        for (int i = 0; i < r; i++) {

            if (pipe(i, 0)) answer++;
        }

        // output
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• r * c 크기의 격자를 2차원 배열 pipeline에 기록하며 탐색을 진행한다. (상태 공간 트리)
• 0열의 시작 행 번호를 0부터 r-1 까지 순서대로 선택하며 탐색을 진행한다.
• pipe() 메서드
  • 현재 위치에서 우상, 우, 우하 순으로 진행 가능하면 파이프를 놓으며 다시 pipe() 메서드를 재귀 호출한다.
  • 만약 끝(c-1열)까지 파이프를 놓았다면 하나의 경우를 찾은 것이므로, true를 반환해서 모든 재귀 메서드를 종료한다.
  • 파이프를 놓지 못해 false를 반환 하더라도, 이미 놓은 파이프 (이미 검사해서 'X'를 채움) 를 다시 '.'으로 바꾸진 않는다. (중복 검사 방지 : 어차피 다른 파이프가 여기에 또 놓더라도 실패할 것임)
• 파이프가 끝까지 도달한 횟수를 출력한다.

---

🔸 end 🔸

• 골드 2 문제였지만, 상태 공간 트리 형식으로 비슷한 문제인 BOJ_6987_월드컵 을 풀고 이어서 풀이해서 간단히 풀 수 있었다.
• 월드컵 보다 난이도가 높은 주요 포인트는 boolean 반환값으로 재귀 메서드를 모두 종료하는 것, 가능한 우상단 쪽으로 파이프를 연결하는 그리디 적 선택, 이미 검사한 좌표는 중복 검사를 하지 않는다는 점 3가지 이다.
  • 중복 검사를 방지하지 않아서 1회 틀렸다. (x를 지우고 다시 '.'을 채웠었다.)