Java | 백준 26169 세 번 이내에 사과를 먹자 문제풀이 및 분석

백준 26169 세 번 이내에 사과를 먹자 문제에 대한 글입니다.

백준 26169 세 번 이내에 사과를 먹자

백준 26169 세 번 이내에 사과를 먹자

문제

문제 정보는 아래 링크에서 확인할 수 있다.

26169번: 세 번 이내에 사과를 먹자

풀이

재귀 호출을 이용한 DFS

재귀호출을 이용해서 깊이 우선 탐색을 진행했다.

• 특징

3의 깊이까지만 탐색을 진행한다. 이를 위해서 깊이 정보를 파악하기 위한 변수 하나를 정의해 주어야 한다.

int depth = 0;

• 경계값 주의

처음 시작하는 지점은 사과의 개수를 파악하지도(직접 제출해 보았다) 않았고 깊이에서도 계산하지 않는다.

전체 코드

public class baekjoon26169 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] map = new int[5][5];
    static int x, y, numOfApple;
    static int[][] var = {{1,0}, {0,1}, {-1,0}, {0,-1}};

    static void input() throws IOException{
        for(int i=0; i<5; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<5; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
    }

    static boolean execute(){
        boolean[][] visited = new boolean[5][5];
        int depth = 0;
        visited[x][y] = true;
        if(map[x][y] == -1) return false;

        dfs(x, y, depth, visited);

        if(numOfApple>=2){
            return true;
        } else {
            return false;
        }
    }

    static void dfs(int x, int y, int depth, boolean[][] visited){
        if(numOfApple>=2 || depth == 3) return;

        for(int i=0 ; i<4; i++){
            int newX = x + var[i][0];
            int newY = y + var[i][1];

            if(newX <0 || newY <0 || newX >=5 || newY >=5) continue;
            if(visited[newX][newY]) continue;
            if(map[newX][newY] == -1) continue;

            depth++;
            visited[newX][newY] = true;
            if(map[newX][newY]==1) numOfApple++;
            dfs(newX, newY, depth, visited);
            if(numOfApple<2) {
                visited[newX][newY] = false;
                depth--;
                numOfApple -= map[newX][newY] == 1 ? 1 : 0;
            }
        }
    }

    public static void main(String[] args) throws IOException{
        input();
        if(execute()){
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
}