[Java] 백준 3109번 : 빵집*

문제

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

3109번: 빵집

 

풀이 과정

대각선 위, 중간, 대각선 아래 순서대로 탐색해서 최대로 설치할 수 있는 개수를 구할 수 있다.

이때, 한 노드에서 갈 수 있는 경로를 모두 탐색했을 때 못가는 경로로 판단날 경우 다시 가볼 필요가 없기 때문에 방문한 모든 노드는 'x'처리한다.

또한, 갈 수 있는 경로는 이제 사용한 경로로 취급되어 다음 경로는 여기를 지나칠 수 없으므로 'x'처리하기 때문에 결과적으로 방문한 모든 노드를 'x'처리하면 된다.

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

public class Main {

    static int R, C;
    static int[] dx = {-1, 0, 1};
    static char[][] map;

    public static void main(String[] args) throws Exception {
        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];

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

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

    public static int dfs(int x, int y){
        if(y == C-1){
            return 1;
        }

        map[x][y] = 'x';
        for(int i=0; i<3; i++){
            int nx = x + dx[i];
            int ny = y + 1;
            if(nx<0 || nx>=R || map[nx][ny] == 'x') continue;
            if(dfs(nx, ny) == 1) return 1;
        }
        return 0;
    }
}

 

결과