[BOJ/DFS] 백준 3109 - 빵집 (Java)

백준 3109 - 빵집

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

문제

빵집이 있는 곳은 RxC 격자로 표현할 수 있음/ 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집
빵집과 가스관 사이에 건물이 있을 수 있고, 건물이 있는 경우 파이프를 놓을 수 없음
가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 함
각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 다각선으로 연결할 수 있고, 각 칸의 중심끼리 연결
가스관과 빵집을 연결하는 파이프라인을 여러 개 설치하는데 이 경로는 겹칠 수 없고, 서로 접할 수 없음 
= 각 칸을 지나는 파이프는 하나여야 함

입력
첫째 줄: R, C (1 <= R <= 10,000, 5 <= C <= 500)
다음 R개 줄: 빵집 근처 모습 (`x`: 건물/ `.`: 빈 칸/ 처음과 마지막 열 항상 비어있음)
출력: 놓을 수 있는 파이프라인 최대 개수

---

풀이

• 시작: (row, 0) / 도착: (? , C - 1)
• 이동 방향: 오른쪽 위, 오른쪽, 오른쪽 아래
  • `int[] dr = {-1, 0, 1}`
  • `int[] dc = {1, 1, 1}`
  • => ex. d = 0 -> (-1, +1): 오른쪽 위

 

DFS

• 종료 조건: `c == C - 1` => 오른쪽 끝 열 도달
• 갈 수 없는 경우
  • 범위 밖: `nr < 0 || nc < 0 || nr >= R || nc >= C`
  • 이미 사용한 칸 or 벽: `visited[nr][nc] || map[nr][nc] == 'x'`
• 방문 처리 + 재귀
  • `dfs(nr, nc)`: 한 번이라도 성공하면 즉시 `true`

static boolean dfs(int r, int c) {
    if (c == C - 1) {
        return true;
    }

    for (int d = 0; d < 3; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];

        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (visited[nr][nc] || map[nr][nc] == 'x') continue;
        visited[nr][nc] = true;

        if (dfs(nr, nc)) return true;
    }

    return false;
}

---

코드

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

// 빵집
public class boj_3109 {
    static int R, C;
    static char[][] map;
    static boolean[][] visited;
    static int[] dr = {-1, 0, 1};
    static int[] dc = {1, 1, 1};
    static int cnt = 0;

    static boolean dfs(int r, int c) {
        if (c == C - 1) {
            return true;
        }

        for (int d = 0; d < 3; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if (visited[nr][nc] || map[nr][nc] == 'x') continue;
            visited[nr][nc] = true;

            if (dfs(nr, nc)) return true;
        }

        return false;
    }

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        for (int i = 0; i < R; i++) {
            visited[i][0] = true;
            if (dfs(i, 0)) cnt++;
        }

        System.out.println(cnt);
    }
}