[BaekJoon] 20208 진우의 민트초코우유 (Java)

1.  문제 링크

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

2.  문제

요약

• 진우는 매일 아침 특정 지역들에서 민트초코우유가 배달된다는 NxN 크기의 2차원 민초마을로 이사하였습니다.
• 진우는 아침에 눈을 뜨면 집에서 민초마을의 지도를 들고 민트초코우유를 찾으러 출발하는데, 이 때 초기 체력은 M입니다.
• 체력은 진우가 이동할 수 있는 거리를 나타냅니다.
• 지도상에서 상, 하, 좌, 우로 1칸씩 이동할 수 있으며 이동하면 체력이 1만큼 줄어듭니다.
• 진우가 민트초코우유를 마신다면 체력이 H만큼 증가하며 진우의 체력이 초기체력 이상으로 올라갈 수 있습니다.
• 체력이 0이 되는 순간 진우는 이동할 수 없습니다.
• 민트초코를 찾으러 돌아다니다가 마을 한복판에서 체력이 0이 되어 집으로 못 돌아가는 상황은 만들어져서는 안됩니다.
• 진우가 집을 나와서 다시 집으로 돌아갈 때까지 마실 수 있는 민트초코우유의 최대 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 10보다 작거나 같은 자연수인 민초마을의 크기인 N, 진우의 초기체력 M, 민트초코우유를 마실 때마다 증가하는 체력의 양 H가 주어지고 두 번째 줄부터 N개의 줄에는 N칸에 걸쳐서 민초마을의 지도가 주어진다.
  • 빈 땅은 0, 진우의 집은 1, 민트초코우유는 2로 주어집니다.
  • 민트초코우유의 총합은 10개를 넘지 않습니다.
• 출력: 첫 번째 줄에 진우가 집을 나와서 다시 집으로 돌아올 때까지 마실 수 있는 민트초코우유의 최대 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	static int[][] map;
	static int h, maxNum = 0;
	static Point home;
	static ArrayList<Point> milks;
	boolean[] visited;
	public void findMaxNum(Point cur_point, int idx, int strength, int count) {
		visited[idx] = true;
		for(int i = 0; i < milks.size(); i++) {
			if(!visited[i]) {
				Point next_milk = milks.get(i);
				int distance = Math.abs(cur_point.x - next_milk.x) + Math.abs(cur_point.y - next_milk.y);
				if(distance <= strength) {
					findMaxNum(next_milk, i, strength - distance + h, count + 1);
				}
			}
		}
		int distance = Math.abs(home.x - cur_point.x) + Math.abs(home.y - cur_point.y);
		if(distance <= strength) {
			maxNum = Math.max(maxNum, count);
		}
		visited[idx] = false;
	}
	
	public void getMaxNum(int n, int init_strength) {
		visited = new boolean[milks.size()];
		for(int i = 0; i < milks.size(); i++) {
			Point milk = milks.get(i);
			int distance = Math.abs(home.x - milk.x) + Math.abs(home.y - milk.y);
			if(distance <= init_strength) {
				findMaxNum(milk, i, init_strength - distance + h, 1);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		map = new int[n][n];
		int init_strength = Integer.parseInt(input[1]);
		h = Integer.parseInt(input[2]);
		milks = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			input = br.readLine().split(" ");
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(input[j]);
				if(map[i][j] == 1) {
					home = new Point(i, j);
				} else if(map[i][j] == 2) {
					milks.add(new Point(i, j));
				}
			}
		}		
		br.close();
		Main m = new Main();
		m.getMaxNum(n, init_strength);
		bw.write(maxNum + "\n");
		bw.flush();
		bw.close();
	}
	
	static class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

4.  접근

• 해당 문제는 백트래킹을 이용하여 해결할 수 있습니다.
• 각 위치를 나타내기 위해 Point라는 class를 생성하고 진우의 집을 나타내는 변수 home과 민트초코우유가 있는 위치를 나타내는 ArrayList milks를 생성합니다.
• 입력받은 민초마을의 지도 정보를 2차원 배열 map에 저장하고 값이 1인 곳은 home에 저장하며 값이 2인 곳들은 milks에 넣어줍니다.
• 각 위치를 방문했는지를 나타내는 2차원 배열 visited를 생성하고 milks에 있는 각 위치들에 대해 반복문을 돌며 진우의 집과 거리가 어느정도 되는지 계산합니다. 이 때 거리 계산은 맨하탄 거리를 이용합니다.
• 만약 계산한 거리가 진우의 초기체력보다 작거나 같다면 해당 위치로 이동할 수 있다는 뜻이므로 해당 위치를 처음 이동할 위치로 잡고 이동합니다.
• 이동한 위치에 대해서는 visited 값을 true로 변경해주고 milks에 있는 위치들을 돌며 다음 이동할 위치를 찾습니다.
• 만약 현재 위치가 아직 방문되지 않았다면, 즉 visited 값이 false라면 해당 위치를 다음 이동할 위치의 후보로 잡고 현재 위치와 해당 위치 사이의 거리를 계산합니다.
• 만약 계산한 거리가 현재 진우에게 남아있는 체력보다 작거나 같다면 해당 위치로 이동할 수 있다는 뜻이기 때문에 해당 위치를 다음 이동할 위치로 잡고 진우의 남아있는 체력에서 거리만큼 빼주어 진우의 남아있는 체력을 갱신합니다. 또한 현재 반복문을 돌고 있는 위치들은 모두 민트초코우유가 있는 위치들이기 때문에 민트초코우유의 개수를 나타내는 인자 count를 1 증가시켜줍니다.
• 재귀함수 호출을 통해 milks의 다른 위치들도 위와 같은 과정을 하며 다음 이동할 수 있는 위치인지 확인합니다.
• 재귀함수 호출을 통해 다른 위치들을 확인하다가 더 이상 진우가 남아있는 체력으로 이동할 수 있는 위치가 없어진다면 마지막 위치에서 진우의 집까지의 거리를 계산하고 해당 거리가 진우의 남아있는 체력보다 작거나 같다면 다시 집으로 돌아갈 수 있기 때문에 집으로 돌아올 때까지 마실 수 있는 민트초코우유의 최대 개수를 나타내는 변수 maxNum을 갱신시켜줍니다. 그리고 다음 탐색 때 이 위치를 다시 방문할 수 있도록 visited 값을 false로 변경시켜줍니다.
• 처음 이동하는 위치의 후보를 milks에 들어있는 모든 위치들로 하여 각 위치에서 백트래킹을 통해 이동할 수 있는 모든 경로들을 탐색하고 모두 마친 후에 maxNum 값을 출력합니다.