[JAVA]3109 빵집

 📚 문제  

3109번: 빵집

 

🔍 아이디어  

원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력하는 문제입니다.

해당 문제를 읽으면서 가장 많은 파이프라인을 연결하기 위해서는 가장 위쪽에 있는것이 최댓값을 구하는경우라 생각했습니다.

갈수 있는길은 대각선위, 옆,대각선 아래이고 각 길에 대한 탐색을 진행합니다.   

각 길을 가는경우 경로가 가능한지 확인하고 만약 노선하나가 연결되어 true를 리턴한다면 나머지 경로에 대해서는 탐색하지 않고 리턴합니다.

 

해당 문제의 포인트는 한번 방문했던 곳은 다시 방문하지 않아도 된다는것입니다. 따라서 어떤 한 점에 진입하는 경우 바로 해당 점에 대한 방문처리를 진행합니다.

 

📝 풀이 

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

public class boj_3109_빵집 {
    private static char[][] map;
    private static int row, col;

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

        st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());

        map = new char[row][col];
        for (int i = 0; i < row; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int cnt = 0;
        for (int i = 0; i < row; i++) {
            if (map[i][0] == 'x') continue;
            if (dfs(0, i)) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    private static boolean dfs(int y, int x) {
        if (y == col - 1) {
            return true;
        } else {
            //오른쪽 위
            map[x][y] = 'x'; //어차피 이미 갔던 길이 안되는 경우는 그 길을 못가는 경우이기에 방문 처리 한다.
            if (0 <= x - 1 && map[x - 1][y + 1] == '.') {
                if (dfs(y + 1, x - 1)) {
                    return true;
                }
            }
            
            //옆
            if (map[x][y + 1] == '.') {
                if (dfs(y + 1, x)) return true;
            }

            //오른쪽 아래
            if (x + 1 < row && map[x + 1][y + 1] == '.') {
                if (dfs(y + 1, x + 1)) return true;
            }
        }
        return false;
    }
}