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

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

 

풀이

집의 위치와 우유의 위치가 주어진다.

 

체력이 0이 되면 이동을 할 수 없다. 우유를 먹으면 일정 체력이 회복되는데 최대한 많은 우유를 먹고 집으로 돌아와야 한다.

 

처음에는 dfs로 풀이를 했는데 시간초과가 발생했다.

 

문제의 조건을 다시 보니 우유의 개수가 10개를 넘지 않는다는 것을 확인했다.

 

지도를 전부 저장하지 않고, 우유의 위치만 list로 저장해줬다.

 

해당 리스트를 탐색하며 우유에 방문처리하면서 진행한다.

 

함수가 실행될 때 현재 위치와 집의 위치의 거리를 계산하여 남아있는 체력으로 돌아올 수 있다면 답을 갱신해줬다.

 

---

 

메모리: 15160KB
시간: 528ms
언어: Java 11

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

public class Main {
    static int[] home;
    static ArrayList<int[]> milkList;
    static int h, answer;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        home = new int[2];
        milkList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int type = Integer.parseInt(st.nextToken());
                if (type == 1) {
                    home[0] = i;
                    home[1] = j;
                } else if (type == 2) {
                    milkList.add(new int[] { i, j });
                }
            }
        }

        answer = 0;
        visited = new boolean[milkList.size()];
        findRoute(home[0], home[1], 0, m);

        System.out.println(answer);
    }

    private static void findRoute(int r, int c, int cnt, int hp) {
        if (Math.abs(home[0] - r) + Math.abs(home[1] - c) <= hp) {
            answer = Math.max(answer, cnt);
        }

        for (int i = 0; i < milkList.size(); i++) {
            int[] milk = milkList.get(i);

            if (visited[i]) {
                continue;
            }

            int dist = Math.abs(milk[0] - r) + Math.abs(milk[1] - c);
            if (dist <= hp) {
                visited[i] = true;
                findRoute(milk[0], milk[1], cnt + 1, hp - dist + h);
                visited[i] = false;
            }
        }

    }

}