[백준][JAVA] - 진우의 민트초코우유(20208)
문제 소개
🥇️ 문제 레벨 : 골드5
🔔 문제 유형 : 백트래킹, 브루트포스
💬 풀이 언어 : JAVA
⏱️ 풀이 시간 : 30분
🖇️ 문제 링크 : 백준 문제 링크
📝 문제
진우는 민트초코우유를 좋아하는 민초단이다. 힘든 일이 있더라도 민트초코우유 하나를 마시면 기운이 펄펄 솟는다고 한다!
민트초코우유를 너무 좋아하는 나머지 진우는 매일 아침 특정 지역들에서 민트초코우유가 배달된다는 N × N 크기의 2차원 민초마을로 이사를 하였다.
진우는 아침에 눈을 뜨면 집에서 민초마을의 지도를 들고 민트초코우유를 찾으러 출발한다. 이때의 초기 체력은 M이다. 여기에서 체력은 진우가 이동할 수 있는 거리를 나타낸다. 진우는 지도상에서 상, 하, 좌, 우로 1칸씩 이동할 수 있으며 이동하면 체력이 1만큼 줄어든다. 진우가 마을을 돌아다니다가 민트초코우유를 마신다면 체력이 H 만큼 증가하며 진우의 체력이 초기체력 이상으로 올라갈 수 있다. 체력이 0이 되는 순간 진우는 이동할 수 없다.
민트초코를 찾으러 돌아다니다가 마을 한복판에서 체력이 0이 되어 집으로 못 돌아가는 상황은 만들어져서는 안된다. 진우가 얼마나 많은 민트초코우유를 마시고 집으로 돌아올 수 있는지 알아보자.
🤔 문제 분석
문제에서 고려할 사항은 다음과 같다.
- 현재 체력이 주어지고, 각 칸을 이동하면 체력이 1씩 줄어든다.
- 민초 우유를 마시면 체력이 M만큼 늘어난다.
- 무조건 집으로 복귀해야 한다.
지도에서 DFS를 통해 탐색하는 방법도 있겠지만, 각 민초 우유의 좌표와 현재 좌표의 차이를 이용해 더 쉽게 구할 수 있다.
예를들어, 집에서 시작해 가장 현재 체력으로 이동할 수 있는 민초 우유의 위치를 보자.
cp : Current Pos / np : Next Pos
# 첫 탐색
현재 체력 : 2
cp : 현재 위치(집) : (6, 3)
np : 다음 위치(우유) : (7, 4)
abs(cp.y - np.y) + abs(cp.x - np.x) = 2
# 두 번째 탐색
현재 체력 : (첫 체력 - 첫 탐색의 이동 거리) + M = 3
cp : 현재 위치(우유) : (7, 4)
np : 다음 위치(우유) : (4, 4)
abs(cp.y - np.y) + abs(cp.x - np.x) = 3
# 세 번째 탐색
현재 체력 : (두 번째 탐색 체력 - 두 번째 탐색의 이동 거리) + M = 3
cp : 현재 위치(우유) : (4, 4)
np : 다음 위치(집) : (6, 3)
abs(cp.y - np.y) + abs(cp.x - np.x) = 3
위처럼 현재 체력으로 이동할 수 있는 모든 민초 우유를 마시면서 이동하면 되므로, 리스트를 생성해 민초 위치를 저장해주면 된다.
for (int y = 0; y < N; y++) {
st = new StringTokenizer(br.readLine());
for (int x = 0; x < N; x++) {
int n = Integer.parseInt(st.nextToken());
if (n == 1) {
homeNode = new Node(x, y);
} else if (n == 2) {
milkList.add(new Node(x, y));
}
}
}
이후 백트래킹을 통해 현재 우유에 대해 방문 처리를 해주고, 다음 우유로 이동하하면서 집으로 복귀할 수 있을 경우 최대값을 갱신해주면 된다.
😎 최종 코드
메모리 : 12532 KB
시간 : 764 ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int N, HP, POTION, max;
static boolean[] visited;
static List<Node> milkList;
static Node homeNode;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 지도의 크기 N * N
N = Integer.parseInt(st.nextToken());
// 초기 HP / 민초 마시고 회복되는 양
HP = Integer.parseInt(st.nextToken());
POTION = Integer.parseInt(st.nextToken());
// 우유가 있는 위치 리스트
milkList = new ArrayList<>();
// init
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int n = Integer.parseInt(st.nextToken());
if (n == 1) {
homeNode = new Node(j, i);
} else if (n == 2) {
milkList.add(new Node(j, i));
}
}
}
st = null;
// 방문 배열 초기화
visited = new boolean[milkList.size()];
// 백트래킹
backTracking(0, homeNode.x, homeNode.y, 0, HP);
// 출력
System.out.println(max);
br.close();
}
private static void backTracking(int depth, int prevX, int prevY,
int cnt, int curHp) {
int distance = getDistance(homeNode.x, prevX, homeNode.y, prevY);
// 현재 위치에서 집까지 돌아갈 수 있다면 최대값 갱신
if (distance <= curHp) {
max = Math.max(max, cnt);
}
// 모든 좌표 중에서 도달할 수 있는 우유 위치 탐색
for (int i = 0; i < milkList.size(); i++) {
Node node = milkList.get(i);
// 이전 위치에서 가고자하는 우유의 위치 까지의 거리 계산
distance = getDistance(prevX, node.x, prevY, node.y);
// 만약 이동해야하는 거리가 체력보다 작고, 방문하지 않았을 경우
if (distance <= curHp && !visited[i]) {
// 기존 체력 저장
int temp = curHp;
// 현재 위치 방문 처리
visited[i] = true;
// 이동하고자하는 좌표까지의 체력 계산
curHp = (curHp - distance) + POTION;
// 백트래킹
backTracking(depth + 1, node.x, node.y, cnt + 1, curHp);
// 탐색 이후 원래 체력으로 복귀
curHp = temp;
// 방문 해제 처리
visited[i] = false;
}
}
}
private static int getDistance(int x1, int x2, int y1, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
static class Node {
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}
댓글남기기