BOJ_G2_3109

📁 [G2_3109] 빵집

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

public class Main {
    static StringTokenizer st;
    static boolean[][] visited;
    static int[][] arr;
    static int R, C;
    static int[] dx = {1, 1, 1};
    static int[] dy = {-1, 0, 1};
    // 파이프라인의 최대 개수
    static int cnt;
    static int nx, ny;

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

        st = new StringTokenizer(br.readLine(), " ");
        // 행
        R = Integer.parseInt(st.nextToken());
        // 열
        C = Integer.parseInt(st.nextToken());

        arr = new int[R][C];

        // true면 건물이나 지나간 자리 , false면 지나갈 수 있는 자리
        visited = new boolean[R + 1][C + 1];

        // 배열 입력
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                arr[i][j] = str.charAt(j);
                if (arr[i][j] == 'x') {
                    visited[i][j] = true;
                }
            }
        }
        for (int i = 0; i < R; i++) {
            dfs(i, 0);
        }
        System.out.println(cnt);

    }

    static boolean dfs(int y, int x) {
        // 기저조건 : 끝에 도착하는 경우 카운팅 ++
        if (x == C - 1) {
            cnt++;
            return true;
        }


        visited[y][0] = true;
        for (int z = 0; z < 3; z++) {
            nx = x + dx[z];
            ny = y + dy[z];


            //못감
            if (nx < 0 || ny < 0 || ny >= R || visited[ny][nx] == true) {
                continue;
            }

            // 갈 수 있는 곳
            if (!visited[ny][nx]) {
                visited[ny][nx] = true;
                if(dfs(ny, nx)){
                    return true;
                }
            }
        }
        return false;
    }
}

🤔 나의 생각

내가 생각한 여기서 키포인트는 최대의 경우를 구하는 것이기 때문에 오른쪽 위 -> 오른쪽 -> 오른쪽 아래 순으로 탐색을 하는 것 이다.
그리고 행마다 나눠서 한 줄을 끝까지 다 가게 되면 그 과정은 끝을 내고 다시 다음 행으로 가서 같은 과정을 진행한다.
기존에 반환값을 void로 받아서 메서드를 끝내야하는데 그전 값으로 돌아가서 메서드에서 나올 수가 없어서 dfs 메서드의 반환값을 boolean으로 설정하였는데 이것이 내가 대면한 문제의 해결책이 되었다.
3방향 탐색과 가지치기만 잘하면 괜찮았던 문제이다.