[백준] 26169 세 번 이내에 사과를 먹자 | DFS, 백트래킹, 그래프 | 실버 Ⅲ | JAVA

📌 문제

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

 

⭐ 풀이 전략

 

1. 문제 접근:
   • 학생이 3번 이내로 이동하며 2개 이상의 사과를 먹을 수 있는지 확인해야 하므로 백트래킹 또는 DFS(깊이 우선 탐색) 을 이용합니다.
   • 조건에 따라 가능한 경로를 탐색하며 사과를 먹을 수 있는지 판단합니다.
2. 탐색 과정:
   • DFS를 통해 현재 위치에서 가능한 모든 방향으로 이동.
   • 이동할 때마다:
     1. 사과를 먹으면 카운트를 증가.
     2. 해당 칸을 장애물로 변경.
   • 재귀 호출 후 원래 상태로 복구(백트래킹).
3. 종료 조건:
   • 이동 횟수가 3을 초과하면 탐색 중단.
   • 사과를 2개 이상 먹으면 탐색 중단 후 결과 반환.

 

⭐ 알고리즘 풀이 과정

1. 입력 처리:
   • 5x5 보드와 학생의 초기 위치를 입력받습니다.
2. DFS 함수 작성:
   • 매개변수: 현재 위치, 남은 이동 횟수, 먹은 사과 개수.
   • 이동할 수 없는 칸(장애물, 범위 밖)이나 이동 횟수 초과 시 종료.
   • 사과를 2개 이상 먹으면 바로 종료.
3. 탐색 방향 설정:
   • 상, 하, 좌, 우를 탐색하기 위한 dx, dy 배열 생성.
4. 결과 출력:
   • 탐색 결과로 사과를 2개 이상 먹을 수 있다면 1, 그렇지 않다면 0 출력.

 

✅ 정답코드

import java.util.Scanner;

public class AppleGame {
    static int[][] board = new int[5][5];
    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1};
    static boolean found = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 보드 입력
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        // 학생의 초기 위치
        int startX = sc.nextInt();
        int startY = sc.nextInt();

        // DFS 탐색
        dfs(startX, startY, 0, 0);

        // 결과 출력
        System.out.println(found ? 1 : 0);
    }

    static void dfs(int x, int y, int moves, int apples) {
        // 종료 조건
        if (moves > 3 || found) return; // 이동 횟수 초과 또는 이미 정답 발견
        if (apples >= 2) {
            found = true;
            return;
        }

        // 기존 상태 저장
        int temp = board[x][y];
        board[x][y] = -1; // 현재 위치를 장애물로 변경

        // 4방향 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위 검사 및 이동 가능 여부 확인
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && board[nx][ny] != -1) {
                dfs(nx, ny, moves + 1, apples + (board[nx][ny] == 1 ? 1 : 0));
            }
        }

        // 상태 복구
        board[x][y] = temp;
    }
}

 

🗒️ 코드 해석

1. DFS 함수:
   • moves: 현재까지 이동한 횟수.
   • apples: 현재까지 먹은 사과 개수.
   • 이동 횟수가 3을 초과하거나 사과 2개 이상을 먹으면 탐색 종료.
2. 상태 복구(백트래킹):
   • 방문했던 칸을 장애물로 변경한 후, 탐색 종료 시 원래 상태로 되돌림.
3. 탐색 방향:
   • dx와 dy를 통해 상, 하, 좌, 우 탐색.

 

💡 문제 해결 포인트

• 최적화: 사과를 2개 이상 먹는 순간 더 이상 탐색하지 않음.
• 백트래킹: 탐색 후 상태를 복구하여 다른 경로 탐색에 영향 주지 않음.
• DFS 탐색: 모든 가능한 경로를 탐색하여 조건 만족 여부를 판단.