[백준] 20208번 : 진우의 민트초코우유

문제

 

접근 방식

문제가 너무 대놓고 그래프로 네 방향을 탐색하라고 나와 있는데 이거에 낚이면 시간초과에 걸린다.

 

장애물이 없는 지도가 주어져서 현재 지점의 좌표와 이동하고자 하는 지점의 좌표의 차를 구하면

몇 칸을 이동해야하는지 알 수 있기 때문에 직접 한 칸씩 움직일 필요가 없다.

 

그래서 집의 좌표와 민초우유의 좌표만 구해두고 집의 위치에서부터 시작해서

현재 좌표와 민초우유의 좌표의 차를 구하고 현재 체력보다 작거나 같다면 이동해주면 된다.

 

풀이

public class Main {

	static int n, m, h, max = 0, milk = 0;
	static Pair home;
	static ArrayList<Pair> milks = new ArrayList<>();
	static boolean[] isVisited;

	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());

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());

				if (x == 1) {
					home = new Pair(i, j);
				} else if (x == 2) {
					milks.add(new Pair(i, j));
					milk++;
				}
			}
		}

		isVisited = new boolean[milk];

		solve(home.x, home.y, 0);

		System.out.println(max);
	}

	static void solve(int x, int y, int eat) {
		for (int i = 0; i < milk; i++) {
			if (isVisited[i]) continue;

			isVisited[i] = true;

			Pair pair = milks.get(i);

			int nx = pair.x;
			int ny = pair.y;
			int distNext = getDist(x, y, nx, ny);

			if (distNext <= m) {
				m += h;
				m -= distNext;
				if (getDist(home.x, home.y, nx, ny) <= m) max = Math.max(max, eat + 1);
				solve(nx, ny, eat + 1);
				m -= h;
				m += distNext;
			}

			isVisited[i] = false;
		}
	}

	static int getDist(int ax, int ay, int bx, int by) {
		return Math.abs(ax - bx) + Math.abs(ay - by);
	}

	static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}