[백준] 진우의 민트초코우유 - Java 20208

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

 

 

브루트 포스 문제이다. 처음에는 그냥 좌표값을 1씩 증가시키면서 전체의 좌표를 돌았는데

역시나 시간 초과가 발생했다.

 

 

따라서, 민트초코우유가 있는 장소를 담고 있는 리스트를 만들어 해당 좌표만 접근하도록 코드를 변경했다.

 

현재 `health`로 해당 좌표에 도달할 수 있다면 해당 부분에 관한 재귀를 돈다.

이때, 현재 위치에서 출발지로 되돌아갈 수 있다면 해당 우유는 먹을 수 있기 때문에 그 경우 최대값을 갱신해줬다. 

 

 

public class BOJ20208 {
    static int N, M, H;
    static int[][] grid;
    static boolean[] visited;
    static List<int[]> mint;
    static int start_y, start_x;
    static int result = 0;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        grid = new int[N][N];
        mint = new ArrayList<>();

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                grid[i][j] = Integer.parseInt(st.nextToken());

                if(grid[i][j] == 1){
                    start_y = i;
                    start_x = j;
                } else if(grid[i][j] == 2){
                    mint.add(new int[]{i, j});
                }
            }
        }

        visited = new boolean[mint.size()];

        dfs(start_y, start_x, 0, M);

        System.out.println(result);
    }

    public static void dfs(int y, int x, int count, int health){
        if((Math.abs(y - start_y) + Math.abs(x - start_x)) <= health){
            result = Math.max(result, count);
        }

        for(int i = 0; i < mint.size(); i++){
            if(!visited[i]){
                int[] curr = mint.get(i);
                if(health >= (Math.abs(curr[0] - y) + Math.abs(curr[1] - x))) {
                    visited[i] = true;
                    dfs(curr[0], curr[1], count + 1, health - (Math.abs(curr[0] - y) + Math.abs(curr[1] - x)) + H);
                    visited[i] = false;
                }
            }
        }
    }
}