[BaekJoon] 3109 빵집 (Java)

1.  문제 링크

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

2.  문제

요약

• 빵집이 있는 곳은 R x C 격자로 표현할 수 있고, 첫째 열은 근처 빵집의 가스관이며, 마지막 열은 원웅이의 빵집입니다.
• 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 하는데, 빵집과 가스관 사이에는 건물이 있을 수도 있으며 건물이 있는 경우에는 파이프를 놓을 수 없습니다.
• 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 합니다.
• 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래로 대각선으로 연결할 수 있습니다.
• 여러 개의 파이프라인을 설치하려고 하는데, 경로를 겹칠 수 없고 서로 접할 수도 없습니다. 즉, 각 칸을 지나는 파이프는 하나이어야 합니다.
• 원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 R과 5보다 크거나 같고 500보다 작거나 같은 C가 주어지고 두 번째 줄부터 R개의 줄에 빵집 근처 모습이 주어집니다. '.'는 빈 칸이고, 'x'는 건물입니다.
  • 처음과 마지막 열은 항상 비어있습니다.
• 출력: 첫 번째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력합니다.

3.  소스코드

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

public class Main {
    static int R, C;
    static char[][] map;
    static int[] dx = {-1, 0, 1}, dy = {1, 1, 1};
    static void input() {
        Reader scanner = new Reader();
        R = scanner.nextInt();
        C = scanner.nextInt();
        map = new char[R][C];

        for(int row = 0; row < R; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < C; col++)
                map[row][col] = info.charAt(col);
        }
    }

    static void solution() {
        int answer = 0;
        boolean[][] visited = new boolean[R][C];

        for(int row = 0; row < R; row++) {
            if(dfs(row, 0, visited))
                answer++;
        }

        System.out.println(answer);
    }

    static boolean dfs(int x, int y, boolean[][] visited) {
        if(visited[x][y]) return false;

        visited[x][y] = true;

        if(y == C - 1) return true;

        for(int dir = 0; dir < 3; dir++) {
            int cx = x + dx[dir], cy = y + dy[dir];

            if(isInMap(cx, cy) && map[cx][cy] == '.' && !visited[cx][cy]) {
                if(dfs(cx, cy, visited)) return true;
            }
        }

        return false;
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < R && y >= 0 && y < C) return true;
        return false;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

4.  접근

• 첫 번째 열의 첫 번째 행부터 마지막 행까지 각 위치를 출발점으로 잡고 각 출발점마다 DFS를 통해 마지막 열까지 파이프라인을 연결하는 작업을 진행합니다.
  • 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선 방향의 위치를 확인하여 해당 위치가 R x C 격자 내에 위치하고 아직 방문하지 않았으며 파이프라인을 연결할 수 있는 곳이라면 해당 위치에 대해서 파이프라인을 연결해나갑니다.
  • 이미 방문한 곳은 visited 배열에 true로 방문 체크를 진행합니다.
  • 만약 이렇게 파이프라인을 연결하다가 마지막 열까지 도착한다면 하나의 파이프라인을 완성했기 때문에 다음 시작점에서 파이프라인을 연결합니다.
  • 파이프라인을 연결할 때, 최대한 많은 파이프라인을 연결하기 위해서 더 작은 행부터, 즉 오른쪽 위 대각선 방향부터 가장 큰 행, 즉 오른쪽 아래 대각선 방향 순으로 파이프라인을 연결하여 다음 시작점에서 파이프라인 연결을 성공할 확률을 높입니다.