[백준 26169] 세 번 이내에 사과를 먹자 (Java) - DFS, 백트래킹

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

세 번 이내에 사과를 먹자

문제

5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸으로 되어 있는 격자로 구분된다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타낸다. 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가한다. 즉, 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)이다.

현재 한 명의 학생이 (r, c) 위치에 있고 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한가지 방향으로 한 칸 이동할 수 있다. 학생이 사과가 있는 칸으로 이동하면 해당 칸에 있는 사과를 1개 먹는다. 장애물이 있는 칸으로는 이동할 수 없다. 학생이 지나간 칸은 학생이 해당 칸을 떠나는 즉시 장애물이 있는 칸으로 변경된다. 즉, 학생이 해당 칸에서 상, 하, 좌, 우 방향으로 한 칸 이동하는 즉시 해당 칸은 장애물이 있는 칸으로 변경된다.

학생이 현재 위치 (r, c)에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력하자.

입력

첫 번째 줄부터 다섯 개의 줄에 걸쳐 보드의 정보가 주어진다. i번째 줄의 j번째 수는 보드의 (i - 1)번째 행, (j - 1)번째 열의 정보를 나타낸다. 보드의 정보가 1이면 해당 칸은 사과가 1개 있는 격자임을 나타내고, 0이면 빈칸이 있는 격자를 나타내고, -1이면 장애물이 있는 격자임을 나타낸다.

다음 줄에 학생의 현재 위치 r, c가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 학생이 현재 위치 (r, c)에서 세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 먹을 수 없으면 0을 출력한다.

제한

• 0 ≤ r, c ≤ 4
• 현재 위치 (r, c)는 빈칸이다.

예제 입력 1 복사

0 0 1 0 0
0 0 -1 0 0
0 0 1 0 0
1 1 -1 1 0
0 0 0 -1 0
4 1

예제 출력 1 복사

1

(4, 1) -> (3, 1) -> (3, 0)으로 이동하면 사과를 2개 먹을 수 있다.

---

풀이

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

public class Main {
    static int[][] A = new int[5][5];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean isPossible = false;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 보드정보 입력받기
        for (int i=0; i<5; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<5; j++){
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 학생위치 입력받기
        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        // 현재 위치는 떠나면 장애물
        A[r][c] = -1;
        DFS(r,c,0,0);

        System.out.println(isPossible ? 1 : 0);

    }
    private static void DFS(int i, int j, int depth, int apple){
        // 이미 성공했다면 탐색 중단
        if (isPossible) return;

        // 사과를 2개이상 먹었다면 성공
        if (apple >= 2){
            isPossible = true;
            return;
        }

        // 이동 3번 초과시 실패
        if (depth == 3) return;

        // 상하좌우 탐색
        for (int n=0; n<4; n++){
            int x = i + dx[n];
            int y = j + dy[n];
            if (!isIn(x,y) || A[x][y] == -1) continue;

            int temp = A[x][y]; // 현재 칸의 값 임시 저장
            int newAppleCount = apple + (temp == 1 ? 1 : 0);

            A[x][y] = -1; // 지나가고 나면 장애물로 바뀜
            DFS(x, y, depth+1, newAppleCount);

            A[x][y] = temp; // 백트래킹
        }
    }
    private static boolean isIn(int x, int y){
        return x>=0 && x<5 && y>=0 && y<5;
    }
}

• DFS, 백트래킹을 활용한 문제
• 조건이 여러개이므로 DFS내에서 조건을 여러개 설정해야 한다.
• 일단 현재 위치에서 이동하고 나면, 장애물이 생기므로 현재위치에서 이동하기전(DFS 수행 전)에 현재 위치에 -1을 입력해서 장애물을 만들어준다.

DFS

private static void DFS(int i, int j, int depth, int apple){
        // 이미 성공했다면 탐색 중단
        if (isPossible) return;

        // 사과를 2개이상 먹었다면 성공
        if (apple >= 2){
            isPossible = true;
            return;
        }

        // 이동 3번 초과시 실패
        if (depth == 3) return;

        // 상하좌우 탐색
        for (int n=0; n<4; n++){
            int x = i + dx[n];
            int y = j + dy[n];
            if (!isIn(x,y) || A[x][y] == -1) continue;

            int temp = A[x][y]; // 현재 칸의 값 임시 저장
            int newAppleCount = apple + (temp == 1 ? 1 : 0);

            A[x][y] = -1; // 지나가고 나면 장애물로 바뀜
            DFS(x, y, depth+1, newAppleCount);

            A[x][y] = temp; // 백트래킹
        }
    }
    private static boolean isIn(int x, int y){
        return x>=0 && x<5 && y>=0 && y<5;
    }

• 입력으로 받은 현재 위치에서 상하좌우를 탐색한다.
• 이동 시, 바로 그 자리에 장애물이 생기기 때문에 되돌아갈수없다(같은 자리 2번지나갈 수 없음)
• 3번 이동 내에, 사과를 2개이상 먹어야 한다.
• DFS 종료조건
  • 이미 성공했다면 탐색 중단
  • 파라미터로 받은 apple이 2개이상이라면 isPossible을 true로 바꾼 뒤, 탐색 중단
  • 이동 3번 초과시(depth) 탐색 중단
• DFS 수행
  • 파라미터로 받은 현재 좌표의 상,하,좌,우 좌표를 탐색한다.
  • 탐색좌표가 유효하고 장애물이 있는게 아니라면
  • 탐색좌표 값을 temp에 임시저장해둔다. (다시 백트래킹 하기 위해)
  • temp의 값이 1(사과)이라면 newAppleCount에 더해준다.
  • 그리고 탐색좌표 A[x][y]에 -1을 입력해서 장애물을 만들어준다.
  • 이후 DFS 재귀호출 (depth증가, apple개수 업데이트)
  • DFS재귀호출을 빠져나온 이후에는 A[x][y]의 이전값(temp)을 입력해서 백트래킹 해준다.