백준 3109번 - 빵집

문제

백준 3109번 - 빵집

아이디어

• 갈 수 있는 방향이 오른쪽, 오른쪽 위, 오른쪽 아래로 정해져 있고 겹칠 수 없을 때 최대한 많은 파이프라인이 설치되기 위해서는 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 위부터 탐색하는 것이 유리하다.
• 이는 재귀 형태로 구현할 수 있고, 마지막 열에 도착했을 때 파이프라인을 놓을 수 있는 것이다.
• 경로는 겹칠 수 없다 했으므로 방문 체크도 잊지 않는다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(R x C)

코드 구현

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

public class BJ_3109 {

    static char[][] map;
    static int r, c;
    static boolean[][] visit;

    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];
        visit = new boolean[r][c];

        for (int i = 0; i < r; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int count = 0;
        for (int i = 0; i < r; i++) {
            count += solve(i, 0);
        }

        System.out.println(count);
    }

    private static int solve(int x, int y) {

        visit[x][y] = true;

        if (y == c - 1) { //파이프라인 연결 성공
            return 1;
        }

        //오른쪽 위
        if (x - 1 >= 0 && map[x - 1][y + 1] == '.' && !visit[x - 1][y + 1]) {
            if (solve(x - 1, y + 1) == 1) {
                return 1;
            }
        }

        //오른쪽
        if (map[x][y + 1] == '.' && !visit[x][y + 1]) {
            if (solve(x, y + 1) == 1) {
                return 1;
            }
        }

        //오른쪽 아래
        if (x + 1 < r && map[x + 1][y + 1] == '.' && !visit[x + 1][y + 1]) {
            if (solve(x + 1, y + 1) == 1) {
                return 1;
            }
        }

        return 0;
    }
}