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

Java

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

문제

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

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

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

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

접근 방법

처음에 BFS를 사용하여, 각 점들을 한칸 씩 이동해보며 우유를 모으는 방법을 사용하였으나 이는 방문 처리를 할 수 없으므로 시간초과가 난다.

문제에서 요구하는 것은 결국 얼마만큼의 초코우유를 모을 수 있는가를 요구하므로,
처음 지점에서 각 우유가 있는 위치들을 탐색하여, 현재 체력으로 갈 수 있으면 계속하여 다음 우유를 찾는 DFS로 해결해야한다.

또한 매번 우유에 도달하였을 때, 집으로 갈 수있는 체력이면 현재까지 모은 우유의 개수를 갱신해 준다.

코드

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

public class Main {
	static int n, M, H, result, count;
	static int[][] map;
	static int homeY;
	static int homeX;
	static boolean[] visH;
	static ArrayList<int[]> milk;
	
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/mainInput.txt"));	//제출 할 때 주석해야함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	M = stoi(stk.nextToken());
    	H = stoi(stk.nextToken());
    	
    	map = new int[n][n];
    	milk = new ArrayList<>();
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			map[i][j] = stoi(stk.nextToken());
    			if(map[i][j] == 1) {
    				homeY = i;
    				homeX = j;
    			}
    			else if(map[i][j] == 2) {
    				count++;
    				milk.add(new int[] {i,j});
    			}
    		}
    	}
    	visH = new boolean[count];
    	DFS(homeY, homeX, M, 0);
    	
    	System.out.println(result);
    	br.close();
	}
	
	// 우유 모으기 시작
	static void DFS(int y, int x, int h, int cnt) {
		int len;
		len = Math.abs(y - homeY) + Math.abs(x - homeX);
		if(len <= h) {		// 현재 우유 위치에서 집에 도달 할 수 있는 거리이면
			result = Math.max(result, cnt);
		}
		
		for(int i = 0; i < count; i++) {
			len = Math.abs(y - milk.get(i)[0]) + Math.abs(x - milk.get(i)[1]);
			// 현재 위치와 각 우유까지의 거리보다 체력이 크다면, 다음 우유를 탐색한다.  
			if(!visH[i] && len <= h) {
				visH[i] = true;
				DFS(milk.get(i)[0], milk.get(i)[1], h - len + H, cnt + 1);
				visH[i] = false;
			}
		}
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

BFS인 것 같지만 DFS였던 나를 속인 문제.

개선할 점

없습니다.