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

 

해당 문제를 보고 백트래킹을 써야겠다는 생각이 들었다.

백트래킹?
모든 가능한 방문 조합을 재귀적으로 시도해보고, 그중에서 유효한 것만 정답 후보로 선택
모든 경우를 탐색하되, 중간에 불가능한 경로는 더 이상 가지 않고 돌아가는 알고리즘

하지만 구현하는 데에 좀 어려움을 겪었다.

처음에 dx, dy로 한칸씩 이동하면서 초코우유를 먹으면서 체력을 늘리고 2를 0으로 바꾼 뒤에 다시 탐색해보는 방향으로 생각했는데 아주 잘못된 생각이었다.

 

 

이 문제의 목표는 최대한 많은 민트초코우유를 먹고, 집에 돌아올 수 있는 경우 중 우유의 최대 개수를 구하는 것이다.

조건은 아래와 같다.

 

• N x N 크기의 마을 (map)
• 진우의 집은 1, 민트초코우유는 2, 빈칸은 0
• 진우는 상하좌우 한 칸 이동에 체력 1 소모
• 민트초코우유를 먹으면 체력 H 회복
• 초기 체력은 M
• 체력이 0이 되면 이동 불가
• 단, 마지막에는 집으로 돌아와야 함

 

해당 문제에서 백트래킹은 아래와 같은 로직으로 실행되어야 한다.

 

• 현재 위치에서 갈 수 있는 우유를 하나씩 선택하고, 선택한 우유를 방문 표시하고, 이동에 따른 체력 계산한다.
• 체력이 0이 되거나, 더 이상 갈 수 있는 우유가 없으면 종료한다.
• 집까지 돌아올 수 있다면 정답 후보로 채택한다.
• 다른 우유부터 먹는 순서도 모두 시도해본다.

 

dfs(현재좌표 x, y, 현재체력 m, 먹은우유개수 count, 방문배열 visited) {
    if (x,y → 집까지 갈 수 있다면)
        answer = max(answer, count);

    for (모든 우유 위치) {
        if (방문 안 했고, 집까지의 거리 ≤ 현재 체력) {
            방문 체크
            dfs(다음 우유 위치, 체력 감소 + 회복, count + 1, visited)
            방문 해제 (백트래킹)
        }
    }
}

 

 

 

 

최종 코드

package baekjoon._20208;

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

public class Main {
	static int N, M, H;
	static int[][] map;
	static int answer = 0;
	static int startX, startY;
	static List<int[]> milks = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		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());
		
		map = new int[N][N];

		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					startX = i;
					startY = j;
				} else if (map[i][j] == 2) {
					milks.add(new int[]{i, j});
				}
			}
		}
		
		boolean[] visited = new boolean[milks.size()];
		dfs(startX, startY, M, 0, visited);
		System.out.println(answer);

	}
	
	static void dfs(int x, int y, int m, int count, boolean[] visited) {
        // 현재 위치에서 집까지 갈 수 있으면 answer 갱신
        int homeDist = Math.abs(x - startX) + Math.abs(y - startY);
        if (m >= homeDist) {
            answer = Math.max(answer, count);
        }

        for (int i = 0; i < milks.size(); i++) {
            if (visited[i]) continue;

            int[] milk = milks.get(i);
            int nx = milk[0];
            int ny = milk[1];
            int dist = Math.abs(x - nx) + Math.abs(y - ny);

            if (m < dist) continue; // 못 감

            visited[i] = true;
            dfs(nx, ny, m - dist + H, count + 1, visited);
            visited[i] = false; // 백트래킹
        }
    }

}