백준_진우의민트초코우유_20208

문제 링크

조건

•  N  : 마을 크기 NxN 
•  M  : 초기체력
•  H  : 회복 체력, 민트초코우유를 마시면 H만큼 회복됨

 

접근 방법

• 민트초코우유의 총합은 10개를 넘지 않음
  • mint 리스트에 10개의 우유 위치를 넣고 부분집합(조합)
  • max(진우가 마실 수 있는 우유의 최대개수)값을 갱신할 수 있는 경우에만 순열 dfs 진행 => 위의 조합으로 선정된 우유들(ori)을 기준으로 마실 순서 정하기 위해
  • 순열 dfs 진행 시, 다음 우유까지 먹으러 갈 체력이 있는지 확인
  • 선정된 우유를 모두 마신 경우(flag == ori) 현 위치에서 집까지 돌아갈 체력이 남아있다면 max값 cnt로 갱신 

 

솔루션

public class Main {

	static int N, M, H;//맵 N*N, 초기체력, 회복체력
	static List<int[]> mint;
	static int max, size;
	static int sr,sc;//집 위치
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		
		mint = new ArrayList<int[]>();//민트초코 위치 저장 => 최대 10개
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine().trim(), " ");
			for(int j = 0; j < N; j++) {
				int m = Integer.parseInt(st.nextToken());
				if(m == 2) {//민트초코
					mint.add(new int[] {i,j});
				}else if(m == 1) {//집
					sr = i;
					sc = j;
				}
			}
		}
		
		size = mint.size();//민트초코 개수
		//부분집합 => 비트마스크 활용
		for(int i = 1; i < (1 << size); i++) {
			int cnt = 0;
			for(int j = 0; j < size; j++) {
				if((i & (1 << j)) > 0) cnt++;
			}
			
			
			if(cnt <= max) continue;//최대값 갱신할 수 있는 경우에만 dfs 
			dfs(sr,sc,0,M,0,i);
		}
		
		
		System.out.println(max);
		
	}
	
	//현 위치 r, c, 먹은 민트초코 개수, 체력, 현재까지 먹은 민트초코 체크 flag, 먹어야할 민트초코 체크 ori
	private static void dfs(int r, int c, int cnt, int stam, int flag, int ori) {
		if(flag == ori) {
			if(Math.abs(r-sr) + Math.abs(c-sc) <= stam) {//집까지 돌아갈 수 있으면
				max = cnt;
			}
			return;
		}
		
		for(int i = 0; i < size; i++) {
			if((ori & (1 << i)) == 0 || (flag & (1 << i)) > 0) continue; //먹을 민트초코가 아니거나, 이미 먹은 민트초코라면 거름
			
			int[] next = mint.get(i);
			//먹으러 갈 수 있는지 확인
			int dis = Math.abs(r - next[0]) + Math.abs(c - next[1]);
			if(dis <= stam) {
				dfs(next[0], next[1], cnt+1, stam - dis + H, flag | (1 << i), ori);
			}
		}
	}
}

 

리뷰

• 부분집합(조합)과 순열을 모두 사용해서 시간초과가 나지 않을까 걱정했지만 민트초코개수가 최대 10개이고, 가지치기를 잘 해주면 됨..!