3109번 빵집

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

처음 생각 : BFS로 첫 열 → 마지막 열 

그러나 바로 방문 처리 등등 몇 초만에 생각 바꿨다.

결국에는

DFS로 첫 열 → 마지막 열로 가는 방법을 선택.

stop은 마지막 열에 도착했을 때, stop을 true로 바꿔주고

그 이후로는 stop이 true면, 방문 처리, 재귀 진행이 안 되게 함수 종료.

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int R, C, answer = 0;
    static char[][] m;
    static int[] dy = {-1, 0, 1};
    static int[] dx = {1, 1, 1};
    static boolean[][] visit;
    static boolean stop;
    
    static int dfs(int r, int c)
    {    
        if(stop) {
            return 0;
        }
        
        if(c == C - 1) {
            if(!visit[r][c]) {
                visit[r][c] = true;
                stop = true;
                return 1;
            }
            return 0;
        }
        
        visit[r][c] = true;
        
        int ret = 0;
        
        for(int i=0; i<3; i++) {
            int y = r + dy[i];
            int x = c + dx[i];
            if(y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || m[y][x] == 'x') {
                continue;
            }
            ret += dfs(y, x);
        }
        
        return ret;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        m = new char[R+1][C+1];
        visit = new boolean[R+1][C+1];
        
        for(int i=0; i<R+1; i++) {
            Arrays.fill(visit[i], false);
        }
        
        for(int i=0; i<R; i++) {
            String s = br.readLine();
            for(int j=0; j<C; j++) {
                m[i][j] = s.charAt(j);
            }
        }
        
        for(int i=0; i<R; i++) {
            stop = false;
            answer += dfs(i, 0);
        }
        
        bw.write(String.valueOf(answer) + "\n");
        bw.flush();
        bw.close();
    }
}