[BOJ261169] 세 번 이내에 사과를 먹자 - JAVA

 

 

문제 #26169

 

시간 제한 1초

메모리 제한 512MB

 

 

 

 

내가 작성한 코드

 

import java.io.*;
import java.util.*;

public class BOJ26169 {

    static StringBuilder sb = new StringBuilder();
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st = null;

    static final int N = 5;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int[][] board = new int[N][N]; // 사과 정보
    static boolean[][] visited = new boolean[N][N]; // 방문 여부 체크
    static boolean isSearch;
    static Pos startPos;
    static class Pos{ // 시작 위치
        int y, x; // y가 행, x가 열
        Pos(int y, int x){
            this.y = y;
            this.x = x;
        }

    }
    public static void main(String[] args) throws Exception {
        input();
        solution();
    }
    static void input() throws Exception{ // 입력데이터 저장
        for(int y=0; y<N; ++y){
            st = new StringTokenizer(reader.readLine(), " ");
            for(int x=0; x<N; ++x){
                board[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(reader.readLine(), " ");

        startPos = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())); // 시작위치
    }
    static void solution(){
        visited[startPos.y][startPos.x] = true; // 현재 시작점은 미리 방문체크
        backtracking(startPos, 0, 0); // 메소드 호출
        if(isSearch){ // 1인 경우를 찾았다면
            System.out.println(1);
        }else{ // 없다면
            System.out.println(0);
        }
    }

    private static void backtracking(Pos pos, int apple, int cnt) { //현재 위치, 사과개수, 움직인 횟수
        if(cnt <=3 && apple >=2){ // 3회 이내로 사과개수가 2개 이상이라면,
            isSearch = true;
            return;
        }
        if(isSearch || cnt >3) return; // 이미 1임을 확인했거나, 3번째가 넘은 4회 움직였다면
        for(int i=0; i<4; ++i) { // 사방탐색
            Pos temp = new Pos(pos.y + dy[i], pos.x + dx[i]); // 임시 포스
            if (!canGo(temp)) continue; // 갈수 없다면 다른 방향 탐색
            if(board[temp.y][temp.x]==1) { // 갈 수 있지만, 갈 곳이 1이라 사과를 먹을 수 있는 경우
                visited[temp.y][temp.x] = true; // board[temp.y][temp.x] = -1 도 가능. 방문 체크
                backtracking(temp, apple + 1, cnt + 1); // 사과를 먹을 수 있으므로, 현재 사과 + 1, 횟수 +1
                visited[temp.y][temp.x] = false; // 방문 체크 해제
                continue;// 아래는 확인할 필요 없으므로 continue
            }
            if(board[temp.y][temp.x]==0) { // 갈수 있지만, 가는 곳이 사과가 없는 빈칸이라면
                visited[temp.y][temp.x] = true; // board[temp.y][temp.x] = -1 도 가능. 방문 체크
                backtracking(temp, apple, cnt + 1); // 사과가 없으므로, 현재 사과 그대로 , 횟수만 + 1
                visited[temp.y][temp.x] = false; // 방문 체크 해제
            }
        }
    }

    private static boolean canGo(Pos pos) { // 갈 수 있는지 확인하는 메소드
        if(!inRange(pos)) return false; // 범위안에 없다면 false 리턴
        if(visited[pos.y][pos.x] || board[pos.y][pos.x] == -1) // 이미 방문해서 돌아갈 수 없는 길이거나, 장애물이 놓여있는 경우
            return false;
        return true;
    }

    private static boolean inRange(Pos pos) { // 인덱스가 0과 N사이에 있는지(보드 안에 있는지) 확인하는 메소드
        return 0<=pos.x && pos.x<N && 0<=pos.y && pos.y<N;
    }

}

배운 것

백트래킹과 bfs의 차이점을 제대로 알아두자.