[Gold V] 진우의 민트초코우유 - 20208
성능 요약
메모리: 12356 KB, 시간: 132 ms
분류
백트래킹, 브루트포스 알고리즘
제출 일자
2024년 6월 15일 19:47:43
문제 설명
진우는 민트초코우유를 좋아하는 민초단이다. 힘든 일이 있더라도 민트초코우유 하나를 마시면 기운이 펄펄 솟는다고 한다!
민트초코우유를 너무 좋아하는 나머지 진우는 매일 아침 특정 지역들에서 민트초코우유가 배달된다는 N × N 크기의 2차원 민초마을로 이사를 하였다.
진우는 아침에 눈을 뜨면 집에서 민초마을의 지도를 들고 민트초코우유를 찾으러 출발한다. 이때의 초기 체력은 M이다. 여기에서 체력은 진우가 이동할 수 있는 거리를 나타낸다. 진우는 지도상에서 상, 하, 좌, 우로 1칸씩 이동할 수 있으며 이동하면 체력이 1만큼 줄어든다. 진우가 마을을 돌아다니다가 민트초코우유를 마신다면 체력이 H 만큼 증가하며 진우의 체력이 초기체력 이상으로 올라갈 수 있다. 체력이 0이 되는 순간 진우는 이동할 수 없다.
민트초코를 찾으러 돌아다니다가 마을 한복판에서 체력이 0이 되어 집으로 못 돌아가는 상황은 만들어져서는 안된다. 진우가 얼마나 많은 민트초코우유를 마시고 집으로 돌아올 수 있는지 알아보자.
입력
첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다.
두번째 줄부터 N+1번째 줄에 N칸에 걸쳐서 민초마을의 지도가 주어진다. 각 칸은 공백을 두고 주어지며 지도상에서 진우의 집은 1, 민트초코우유는 2로 주어지며 빈 땅은 0으로 주어진다. 진우의 집은 무조건 한 곳이 주어지며 마을에 배달되는 민트초코우유의 총합은 10개를 넘지 않는다.
출력
진우가 집을 나와서 다시 집으로 돌아올 때 까지 마실 수 있는 민트초코우유의 최대 개수를 출력하자.
접근 방법
1. 각 집에서 우유로 가는 거리를 미리 구해준다.
2. 현재 집을 기준으로 체력으로 갈 수 있는 우유를 확인한다.
3. 방문하지 않은 우유를 차근차근 방문해주면서 만약 현재 위치에서 집을 갈 수 있고 우유가 최대값이라면 갱신
4. 맨허튼 거리를 이용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
/**
* 문제: BOJ_20208_G5_진우의 민트초코우유
* 메모리: 12276KB
* 시간: 120ms
* 접근 방법
* 1. 각 집에서 우유로 가는 거리를 미리 구해준다.
* 2. 현재 집을 기준으로 체력으로 갈 수 있는 우유를 확인한다.
* 3. 방문 하지 않은 우유를 차근차근 방문해주면서 만약 현재 위치에서 집을 갈 수 있고 우유가 최대값으로 갱신된다면 기록
*/
public class Main {
static ArrayList<int[]> milk = new ArrayList<>();
static boolean[] eat;
static int[] homeDist;
static int N, H, milkCount, result;
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());
int M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
int sX = 0, sY = 0;
// Input
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int val = Integer.parseInt(st.nextToken());
if (val == 1) {
sX = i;
sY = j;
} else if (val == 2) {
milk.add(new int[]{i, j});
milkCount++;
}
}
} // Input End
// 각 우유에서 집으로 가는 거리를 구함
homeDist = new int[milkCount];
for(int i = 0; i < milkCount; i++) {
int[] m = milk.get(i);
homeDist[i] = getDist(sX,sY,m[0],m[1]);
}
eat = new boolean[milkCount];
solve(sX, sY, M, 0);
System.out.println(result);
}
private static void solve(int x, int y, int move, int eatCount) {
// 이미 최대값만큼 먹었거나 움직일 수 없다면 멈춤
if (result == milkCount) {
return;
}
for (int i = 0; i < milk.size(); i++) {
int[] m = milk.get(i);
int d = getDist(x, y, m[0], m[1]);
// 갈 수 없거나 먹은 적 있다면 넘어간다.
if (d > move || eat[i]) {
continue;
}
int nextMove = move - d + H;
if(nextMove >= homeDist[i] && eatCount + 1 > result) {
result = eatCount + 1;
}
eat[i] = true;
solve(m[0], m[1], nextMove, eatCount + 1);
eat[i] = false;
}
}
private static int getDist(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 1092번 : 배 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |
---|---|
[백준] 2229번 : 조 짜기 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |
[백준] 22866번 : 탑 보기 Gold3(골드3) - JAVA[자바] (1) | 2024.06.14 |
[백준] 1082번 : 방 번호 Gold3(골드3) - JAVA[자바] (1) | 2024.06.13 |
[백준] 1113번 : 수영장 만들기 Gold1(골드1) - JAVA[자바] (0) | 2024.06.11 |