Baekjoon_20208_진우의 민트초코우유

문제 설명

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

• 초기 체력 M
• 상하좌우 1칸씩 이동 - 체력 1씩 저하
• 마을에서 민초를 마시면 H만큼 체력 증가
• 체력 0 - 이동 못함
• 무조건 집으로 돌아와야 함

 

문제 풀이

DFS인지 BFS인지 생각하다가 방문처리에 대한 해법이 생각나지 않아 DFS로 해결했다.

 

우선 민트초코의 위치를 배열에 입력받아 저장하고, 집의 위치도 저장했다.

 

이후 DFS를 수행하는데, DFS의 방문처리로는 비트마스킹을 이용했다.

 

현재 위치에서 민초까지의 거리를 측정한 후, 방문하지 않았고 현재 체력으로 갈 수 있는 거리면 방문처리 후 이동. 돌아왔을 때에는 XOR을 이용해 방문처리를 제거해주었다.

 

이동할 때 마다 (체력 - 이동거리 + 민초 에너지)로 에너지를 계산했다.

 

현위치 - 집 거리를 측정하고 이동할 수 있는 체력과 현재 민초가 max값 보다 크면 집으로 돌아간 후 최대값을 비교했다.

 

문제 풀이 코드

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

public class _20208_진우의민트초코우유 {
	static class Node {
		int r, c;

		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static Node home, mincho[];
	static int N, M, H, minchoNum = 0, max = 0, visited = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		mincho = new Node[10];
		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; ++j) {
				String str = st.nextToken();
				if (str.equals("2")) {
					mincho[minchoNum++] = new Node(i, j);
				} else if (str.equals("1")) {
					home = new Node(i, j);
				}
			}
		}
		dfs(home.r, home.c, M, 0, false);
		System.out.println(max);
	}

	static void dfs(int r, int c, int power, int count, boolean arriveHome) {
		if (arriveHome) { // 집에 도착했을 때
			max = Math.max(max, count);
			return;
		}

		for (int i = 0; i < minchoNum; ++i) {
			if ((visited & (1 << i)) > 0) // 이미 방문한 민초라면 건너뛰기
				continue;

			int distance = Math.abs(r - mincho[i].r) + Math.abs(c - mincho[i].c);	//현위치 -> 다음 민초
			if (distance > power) // 지금 체력으로 갈 수 없는 거리라면 건너뛰기
				continue;

			visited |= (1 << i); // 방문처리
			dfs(mincho[i].r, mincho[i].c, power - distance + H, count + 1, false);
			visited ^= (1 << i); // 방문처리 해제
		}

		int distHome = Math.abs(r - home.r) + Math.abs(c - home.c);	//현위치 -> 집
		if (distHome <= power && count > max) { // 현재 위치에서 집에 갈 수 있는 체력이 남았다면, 최댓값보다 count가 크다면
			dfs(home.r, home.c, power - distHome, count, true);
		}
	}
}