[백준 / 골드2] 3109 빵집 (Java)

문제 보기

사용한 것

• 파이프를 컬럼 마지막 인덱스까지 연결시키기 위한 DFS
• 설치할 파이프 방향을 최선으로 선택하기 위한 그리디

풀이 방법

가장 아래 row 부터 시작하여
- 오른쪽 아래 대각선
- 오른쪽
- 오른쪽 위 대각선
순서로 탐색해야 최선의 결과이다.
다음 row 시작시 탐색할 수 있는 조건이 더 많아지기 때문이다.

• isEmpty에 빈 공간이면 true, 건물이면 false 입력 받음
• row 수(r)만큼 r - 1부터 for 문을 돌며 해당 row 인덱스, 0(col)으로 dfs() 시작한다.
  • 방문할때마다 해당 좌표의 isEmpty를 false로
  • 현재 y가 c - 1이면 끝까지 파이프를 연결했으므로 answer 증가, return true
  • 오른쪽 아래 대각선, 오른쪽, 오른쪽 위 대각선 순서로 재귀하며 각 재귀 결과가 true면 return true
  • 모든 재귀 결과가 false면 return false

코드

public class Main {

    private static int r;
    private static int c;
    private static boolean[][] isEmpty;
    private static int answer;

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String line;
        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        isEmpty = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            line = br.readLine();
            for (int j = 0; j < c; j++) {
                isEmpty[i][j] = line.charAt(j) == '.';
            }
        }

        // DFS
        for (int i = r - 1; i >= 0; i--) {
            int[] path = new int[c];
            path[0] = i;
            dfs(i, 0);
        }

        System.out.println(answer);
    }

    public static boolean dfs(int x, int y) {
        isEmpty[x][y] = false;
        if (y == c - 1) {
            answer++;
            return true;
        }

        // 오른쪽 아래 대각선
        int ny = y + 1;
        int nx = x + 1;
        if (!isOOB(nx, ny) && isEmpty[nx][ny]) {
            if (dfs(nx, ny)) {
                return true;
            }
        }
        // 오른쪽
        nx = x;
        if (!isOOB(nx, ny) && isEmpty[nx][ny]) {
            if (dfs(nx, ny)) {
                return true;
            }
        }
        // 오른쪽 위 대각선
        nx = x - 1;
        if (!isOOB(nx, ny) && isEmpty[nx][ny]) {
            if (dfs(nx, ny)) {
                return true;
            }
        }

        return false;
    }

    public static boolean isOOB(int x, int y) {
        if (x < 0 || x >= r || y < 0 || y >= c) {
            return true;
        }
        return false;
    }
}