[BOJ-14503][백트래킹/DFS] 빵집 - Java

문제 바로가기

3109번: 빵집

 

2차원 배열에서 맨 왼쪽에서 맨 오른쪽까지 갈 수 있는 경로의 최대 개수를 구하는 문제입니다.

삼방 탐색으로 쭉~~ 가주면 됩니다.

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

public class Main{
    static int[] dy = {-1, 0, 1};
    static int[] dx = {1, 1, 1};
    static int R, C, answer;
    static char[][] map;
    static boolean[][] v;

    static class Dir{
        int y, x;
        Dir(int y ,int x){
            this.y = y; this.x = x;
        }
    }

    public static boolean isIn(Dir c) {
        if(0<= c.y && c.y < R && 0 <= c.x && c.x < C) return true;
        else return false;
    }

    public static boolean dfs(Dir cur) {
        if(cur.x == C - 1) return true;

        for(int i = 0; i < 3; i++) {
            Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
            if(!isIn(next) || v[next.y][next.x] || map[next.y][next.x] == 'x') continue;

            v[next.y][next.x] = true; 
            if(dfs(next)) return true;
        }
        return false;
    }

    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];
        v = new boolean[R][C];

        for(int i = 0; i < R; i++) map[i] = br.readLine().toCharArray();
        for(int i = 0; i < R; i++) answer = dfs(new Dir(i, 0)) == true ? answer+1 : answer;

        System.out.println(answer);
    }
}

맨 처음 생각할 때는 끝까지 갈 수 없는 경우 다시 돌아오면서 v 배열을 false로 바꿔줬었는데 이럴 필요가 없습니다.

왜냐면 어차피 true가 된 상태에서 옆으로 나아갈 수 없다면 다른 곳에서 거길 가봤자 끝까지 갈 수 없기 때문입니다.

 

그리고 하나 신경써줘야 할게 이씀니다. 맨 오른쪽에 도착했을 때 true를 리턴하고, 고 앞에서 호출할 때 리턴 값이 true일때 빠져나와야 합니다. 걍 바로 dfs(next) 리턴하면 그 뒤에를 체크를 안해주니까여.

제가 실수했어서 언급합니다 헤헤

 

 

 

감사합니다~!