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

🔎문제

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

3109번: 빵집

 

💡풀이

왼쪽에서 오른쪽으로, 건물을 피해서 파이프라인을 설치한다.

이때 주의할 점이 있다. 문제에는 '각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있다' 고 되어있지만, 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 순서로 봐야 한다는 것이다.

최대한 위쪽으로 파이프를 밀착시켜 최대한 많은 파이프를 설치하도록 하는 것이다.

 

또, 이미 탐색했지만 파이프가 설치되지 않은 곳은 더 이상 방문해도 해당 지점을 지나 만들수있는 파이프는 없다는 뜻이므로 다시 방문하지 않는다.

 

따라서 그리디 + DFS를 활용한 문제이다.

 

📃소스코드

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


public class Main {

    public static int r;
    public static int c;
    public static int[] dx = {-1, 0, 1}; // 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선
    public static int[] dy = {1, 1, 1};
    public static char[][] matrix;
    public static boolean[][] visited;

    public static boolean dfs(int x, int y) {
        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 &&
                !visited[nx][ny] && matrix[nx][ny] == '.') {
                visited[nx][ny] = true;
                if (dfs(nx, ny)) 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());
        matrix = new char[r][c];
        visited = new boolean[r][c];
        for (int i = 0; i < r; i++) matrix[i] = br.readLine().toCharArray();

        int cnt = 0;
        for (int i = 0; i < r; i++) {
            if (matrix[i][0] == 'x') continue;
            if (dfs(i, 0)) cnt++;
        }

        System.out.println(cnt);
    }
}