[ BOJ ][JAVA][20208] 진우의 민트초코우유

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

20208번: 진우의 민트초코우유

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	565	253	187	48.571%

문제

진우는 민트초코우유를 좋아하는 민초단이다. 힘든 일이 있더라도 민트초코우유 하나를 마시면 기운이 펄펄 솟는다고 한다!

민트초코우유를 너무 좋아하는 나머지 진우는 매일 아침 특정 지역들에서 민트초코우유가 배달된다는 N × N 크기의 2차원 민초마을로 이사를 하였다.

진우는 아침에 눈을 뜨면 집에서 민초마을의 지도를 들고 민트초코우유를 찾으러 출발한다. 이때의 초기 체력은 M이다. 여기에서 체력은 진우가 이동할 수 있는 거리를 나타낸다. 진우는 지도상에서 상, 하, 좌, 우로 1칸씩 이동할 수 있으며 이동하면 체력이 1만큼 줄어든다. 진우가 마을을 돌아다니다가 민트초코우유를 마신다면 체력이 H 만큼 증가하며 진우의 체력이 초기체력 이상으로 올라갈 수 있다. 체력이 0이 되는 순간 진우는 이동할 수 없다.

민트초코를 찾으러 돌아다니다가 마을 한복판에서 체력이 0이 되어 집으로 못 돌아가는 상황은 만들어져서는 안된다. 진우가 얼마나 많은 민트초코우유를 마시고 집으로 돌아올 수 있는지 알아보자.

입력

첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다.

두번째 줄부터 N+1번째 줄에 N칸에 걸쳐서 민초마을의 지도가 주어진다. 각 칸은 공백을 두고 주어지며 지도상에서 진우의 집은 1, 민트초코우유는 2로 주어지며 빈 땅은 0으로 주어진다. 진우의 집은 무조건 한 곳이 주어지며 마을에 배달되는 민트초코우유의 총합은 10개를 넘지 않는다.

출력

진우가 집을 나와서 다시 집으로 돌아올 때 까지 마실 수 있는 민트초코우유의 최대 개수를 출력하자.

예제 입력 1

10 2 3
0 0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0
0 2 0 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0
0 2 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 2 0
0 0 0 1 0 0 2 0 0 0
0 0 0 0 2 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0

예제 출력 1

2

좌측 상단을 (0, 0)이라고 하자. 진우의 집은 (6, 3)에 위치한다. 진우가 이동하는 위치, 체력을 순서대로 표시하면 아래와 같다.

• (6, 3) 2
• (7, 4) 3
• (4, 4) 3
• (6, 3) 0

예제 입력 2

6 8 3
0 0 1 0 0 0
0 2 0 2 0 0
0 0 0 0 0 2
0 0 0 0 0 0
2 0 0 2 2 2
0 0 2 0 0 0

예제 출력 2

8

코드

/**
 * BOJ 20208 
 * 진우의 민트초코우유
 * 구현 & permutation & bitmask
 */
import java.io.*;
import java.util.*;

public class p20208 {
    static class Point {
        int r, c;
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static int n, m, h;
    static int[][] map;
    static Point home;
    static List<Point> list;
    static int visited = 0;
    static int ans;
    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()); // 민트초코의 체력 증가량

        list = new ArrayList<>();

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

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1) {
                    home = new Point(i, j);
                } else if (map[i][j] == 2) {
                    list.add(new Point(i, j));
                }
            }
        }

        go(home.r, home.c, m, 0, false);        
        System.out.println(ans);
    }
    static void go(int r, int c, int hp, int count, boolean goBackHome) {
        if (goBackHome) {
            ans = Math.max(ans, count);
            return;
        }

        for (int i = 0; i < list.size(); i++) {
            if ((visited & (1 << i)) > 0) { // 이미 방문된 곳
                continue;
            }
            int distance = Math.abs(r - list.get(i).r) + Math.abs(c - list.get(i).c);
            if (distance > hp) continue; // 현재 hp로 갈 수 없는 거리

            visited |= (1 << i); // 방문
            go(list.get(i).r, list.get(i).c, hp - distance + h, count + 1, false);
            visited ^= (1 << i); // 방문 해제
        }

        int distanceHome = Math.abs(r - home.r) + Math.abs(c - home.c);
        if (distanceHome <= hp && count > ans) { // 현재 위치에서 집에 갈 수 있다면 && 최대값이 갱신된다면
            go(home.r, home.c, hp - distanceHome, count, true);
        }
    }
}