[백준 - 20208] 골드5 - 진우의 민트초코우유(java)

www.acmicpc.net/problem/20208

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

1. 유형

• 순열
• 시뮬

2. 풀이

• 구현기능
  • 민트에 대한 순열
  • 다음 민트까지의 계산
• 자료구조
  • 민트가 몇개인지 모르기때문에 ArrayList사용
  • 좌표저장 Pair 클래스

 

 

민트초코가 10개 밖에 되지 않는다.

 

그러므로 10!경우의 순열을 구한다

 

집에서 -> 민트1 -> 민트2 -> .... 민트10-> 집 까지의 시뮬레이션을 돌린다

 

만약 중간에 체력이 떨어져서 다음 민트로 갈수 없다면 반복문을 종료한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N, M, H, max = 0;
	static boolean visit[];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, -1, 1 };
	static int sr,sc;
	static ArrayList<Pair> p;
	static class Pair{
		int r,c;
		public Pair(int r, int c) {
			// TODO Auto-generated constructor stub
			this.r=r;
			this.c=c;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		H = Integer.valueOf(st.nextToken());
		int map[][] = new int[N][N];
		p = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.valueOf(st.nextToken());
				if (map[i][j] == 1) {
					sr = i;
					sc = j;
				}else if(map[i][j]==2) {
					p.add(new Pair(i,j));
				}
			}
		}
		visit = new boolean[p.size()];
		int arr[] = new int[p.size()];
		perm(0, arr);
		System.out.println(max);
	}
	static void perm(int idx, int arr[]) {
		if(idx==p.size()) {
			findMint(arr);
			return;
		}
		for(int i=0; i<p.size(); i++) {
			if(visit[i]) continue;
			visit[i]=true;
			arr[idx] = i;
			perm(idx+1, arr);
			visit[i]=false;
		}
	}
	
	static void findMint(int arr[]) {
		int hp = M;
		int r=sr;
		int c=sc;
		int cnt=0;
		for(int i=0; i<arr.length; i++) {
			//거리구하기
			int k = arr[i];
			int dist = Math.abs(r-p.get(k).r)+Math.abs(c-p.get(k).c);
			int toHome = Math.abs(sr-p.get(k).r)+Math.abs(sc-p.get(k).c);
			if(hp >= dist) {//다음 민트 찾으러감
				cnt++;
				hp -= dist;//체력씀
				hp += H;//회복
				if(hp >= toHome) {//집 갈 체력이 됨
					max = max < cnt ? cnt : max;//간다
				}
				r = p.get(k).r;
				c = p.get(k).c;
			}
			else {
				return;
			}
		}
	}
}

 

클래스 안 쓴 더 깔끔한 코드

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

public class Solution {
	static int N, M, H, map[][], answer;
	static int[] home;
	static List<int[]> mints;
	static boolean used[];
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st  = new StringTokenizer(bf.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		H = stoi(st.nextToken());
		init();
		for(int i=0; i<N; i++) {
			st  = new StringTokenizer(bf.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = stoi(st.nextToken());
				if(map[i][j]==1) {
					home =new int[]{i,j};
				}else if(map[i][j]==2){
					mints.add(new int[] {i,j});
				}
			}
		}
		used = new boolean[mints.size()];
		permu(0, new ArrayList<>());
		System.out.println(answer);
	}
	static void permu(int depth, List<int[]> list) {
		if(depth == mints.size()) {
			simul(list);
			return;
		}
		for(int i=0; i<mints.size(); i++) {
			if(!used[i]) {
				used[i] = true;
				list.add(mints.get(i));
				permu(depth+1, list);
				used[i] = false;
				list.remove(depth);
			}
		}
	}
	static void simul(List<int[]> list) {
		int cur[] = home.clone();
		int curH = M;
		int cnt = 0;
		for(int[] mint: list) {
			int dist = Math.abs(cur[0]-mint[0]) + Math.abs(cur[1]-mint[1]);
			if(dist > curH) {//거리가 더 먼 경우
				break;
			}else {//거리가 되는 경우
				curH -= dist;
				curH += H;
				cnt++;
				cur = new int[] {mint[0], mint[1]};
				//집까지 돌아가는 경우
				int tohome = Math.abs(home[0]-mint[0]) + Math.abs(home[1]-mint[1]);
				if(tohome <= curH) {
					answer = Math.max(answer, cnt);
				}
			}
		}
	}
	
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
	
	static void init() {
		map = new int[N][N];
		mints = new ArrayList<>();
		answer = 0;
	}
}

4. 느낀점

 

처음엔 집에서 dfs로 4방향 탐색해서 모두 구하려고 했다.

시간초과가 나서, 다른 풀이로 고쳤다.

처음 풀기전부터 시간 복잡도를 생각하고 푸는 연습을 해야겠다.