문제
마라톤 애호가들이 많이 사는 한 도시에서는 해마다 시내에서 마라톤 대회가 개최되고 있다. 이 마라톤 대회의 특징은 주최측에서 출발지와 도착지만 제시하고, 달리는 경로는 참가자 본인이 원하는 대로 결정한다는 점이다. 시내의 도로는 아래 ‘그림 1’에서 보인 것처럼 격자 모양으로 되어 있으며, 격자의 교차점 간의 거리는 모두 동일하기 때문에 1로 간주한다. ‘그림1’에서 보면, 격자상의 교차점의 위치는 편의상 수학에서 사용하는 ( x , y )-좌표로 표기하였고, 좌측 하단의 위치를 (0,0)으로 하였다. 그리고, 각 교차점은 고도가 서로 다른데, 교차점 ( i,j) 고도를 나타내는 정보 aij 는 대괄호 “[ ]” 내에 정수로 표기하였다. 마라톤 대회의 출발지는 (0,0)이며 도착지는 ( M,N )이다. 그리고, 교차점 중 몇 군데에는 참가자들이 달리면서 물을 마실 수 있도록 생수통이 준비되어 있다. 생수통이 준비된 교차점은 그림에서 보듯이 “○”로 표시되어 있고, 그 곳을 지나는 모든 주자들에게 생수통 한 개씩을 제공한다.
오랫동안 이 대회에 참가해 온 철수는 그 동안의 경험에 의해 출발지에서 도착지까지 최단거리 ( M+N 길이의 경로 )만 달린다고 한다. 그리고, 본인이 마라톤을 완주하기 위해 필요로 하는 생수통이 최소 몇 개인지를 알고 있고, 교차점 간의 고도차이가 적으면 적을수록 달리기가 쉽다는 것도 알고 있다. 다시 말해서, 오르막에서는 경사 때문에 달리기가 힘들고, 내리막에서는 자기의 페이스를 조절하기가 쉽지 않아서, 오르막이든지 내리막이든지 고도차이에 비례하여 달리기는 어려워진다는 것을 안다. 따라서, 마라톤 대회가 시작하기 전에 철수는 출발지에서 도착지까지 최단거리 경로 중에서 철수가 필요한 생수통 개수 이상을 얻을 수 있고, 교차점간의 “고도 차이의 합”이 최소인 경로를 찾아야 한다.
마라톤 경로에 대한 정보 즉, 도착점의 위치 (M,N), 각 교차점의 고도, 그리고 생수통이 준비된 곳에 대한 정보가 주어지고, 철수가 필요로 하는 생수통 개수가 주어질 때, 철수가 달려야 할 경로를 선정하는 것을 도와 주려고 한다.
예를 들어, ‘그림 2’에서 보인 것과 같은 마라톤 경로가 있을 때, 출발지에서 도착지까지 갈 수 있는 서로 다른 경로는 4 가지가 있다.
경로 ① : (0,0) → (1,0) → (2,0) → (3,0) → (3,1) <1, 9>
경로 ② : (0,0) → (1,0) → (2,0) → (2,1) → (3,1) <2, 5>
경로 ③ : (0,0) → (1.0) → (1,1) → (2,1) → (3,1) <3, 7>
경로 ④ : (0,0) → (0,1) → (1,1) → (2,1) → (3,1) <3, 9>
“경로 ① ~ ④”의 마지막에 있는 화살괄호 “< >” 속에는 두 정수가 있는데, 이 중 첫째 수는 그 경로를 따라 달릴 때 구할 수 있는 생수통의 개수를 나타내고, 둘째 수는 경로 상에 있는 교차점 간의 “고도 차이의 합”을 나타낸다.
만약 ‘그림 2’에서, K 의 값이 1이라면 철수가 선택해야 할 경로는 “경로 ②” 이고, 그 이유는, 4 가지 모든 경로에서 1 개 이상의 생수통을 구할 수 있지만, 그 중 고도차이의 합이 최소인 값은 5이기 때문이다. 만약, K 의 값이 3이라면 철수가 선택해야 할 경로는 “경로 ③” 이며, 그 이유는, 3개 이상의 생수통을 구할 수 있는 경로는 “경로 ③”과 “경로 ④” 두 가지이고, 그 중 “고도 차이의 합”이 최소인 값은 7이기 때문이다.
철수가 K 개 이상의 생수통을 확보할 수 있는 최단경로( M+N 길이인 경로) 중, 경로 상에 있는 교차점 간 “고도 차이의 합”이 최소가 되는 경로를 찾고 그 값을 출력하는 프로그램을 작성하라. 철수가 달리는 M+N 경로에서 철수가 최소로 필요로 하는 K 개의 생수통을 구할 수 있는 경로는 반드시 하나 이상 있다. 그리고, 출발지에는 생수통이 비치되어 있지 않다.
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에는 케이스의 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다. ( 1≤T≤25 ) 각각의 테스트 케이스 첫 번째 줄에는 도착점의 위치를 나타내는 정수 M,N ( 1≤M,N≤100 )과 철수가 최소로 필요로 하는 생수통의 개수를 나타내는 정수 K ( 0≤K≤10 )가 빈칸(공백)을 사이에 두고 차례로 주어진다. 참고로, 출발점에는 생수통이 비치되어 있지 않기 때문에 생수통이 비치될 수 있는 후보지는 도착점을 포함하여 총 ( M ⅹ N+M+N )곳이고, K 의 최대값은 minimum(10 , M ⅹ N+M+N )이다. 그리고, 이어지는 ( N+1 )개의 줄 각각에는 각 교차점의 고도를 나타내는 ( M + 1 )개의 정수가 주어진다. 즉, 첫 번째 줄에는 a00,a10,a20,…,aM0 가 빈칸(공백)을 사이에 두고 차례로 주어지고, 다음 줄엔 줄에는 a01,a11,a21,…,aM1 이, 마지막 줄엔 a0N,a1N,a2N,…,aMN 이 차례로 주어진다. 생수통이 놓여진 교차점의 위치는 aij의 값을 이용해 표시한다. 만약 aij값이 음수이면 이는 교차점 (i,j)에 생수가 비치되어 있다는 것을 의미하며, 그 교차점의 고도는 |aij|이다. 모든 교차점의 실제 고도는 1이상 100이하이다. 즉, 1≤|aij|≤100이다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에는 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다. 그 다음 줄에는 철수가 K개 이상의 생수통을 확보할 수 있는 최단경로(길이가 M+N인 경로) 중, 경로 상에 있는 교차점 간 “고도 차이의 절대값 합”의 최소값을 출력한다.
import java.util.Arrays;
import java.util.Scanner;
class Solution {
static int total_diff;
static int M, N, K, S;
static int[][] map;
static boolean[][] water;
static int[] prev_diff, prev_water;
static int[][] XY;
static int check(int[] start, int[] temp, int min) {
int x,y;
int cnt=0;
if(S<0) {
x=0;y=0;
total_diff = 0;
} else {
x=XY[S][0];y=XY[S][1];
total_diff = prev_diff[S];
cnt = prev_water[S];
}
for(int i=S+1; i<start.length; i++) {
if(start[i]==0) { // 오른쪽
if(water[x][++y]) cnt++;
XY[i][0] = x; XY[i][1] = y;
total_diff += Math.abs(map[x][y]-map[x][y-1]);
} else if(start[i]==1) { // 위쪽
if(water[++x][y]) cnt++;
XY[i][0] = x; XY[i][1] = y;
total_diff += Math.abs(map[x][y]-map[x-1][y]);
}
prev_diff[i] = total_diff;
prev_water[i] = cnt;
if(total_diff >= min) {
for(int j=M-1; j>=0; j--) {
if(temp[j] >= i) temp[j] = N+j;
else break;
}
Arrays.fill(start, 1);
for(int j=0; j<M; j++) start[temp[j]] = 0;
return min;
}
}
if(cnt>=K) {
min = total_diff;
}
return min;
}
static void update(int[] arr, int[] start) {
for(int i=M-1; i>=0; i--) {
if(arr[i] != N+i) {
S=arr[i]-1;
arr[i]++;
for(int j=i+1; j<M; j++) {
arr[j] = arr[j-1]+1;
}
break;
}
}
Arrays.fill(start, 1);
for(int i=0; i<M; i++) start[arr[i]] = 0;
}
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int test_case = 0; test_case < T; test_case++) {
M = sc.nextInt();
N = sc.nextInt();
K = sc.nextInt();
map = new int[N+1][M+1];
water = new boolean[N+1][M+1];
int[] temp = new int[M];
S = -1;
for(int i=0; i<M; i++) temp[i] = i;
for(int i=0; i<=N; i++) {
for(int j=0; j<=M; j++) {
map[i][j] = sc.nextInt();
if(map[i][j]<0) {
water[i][j] = true;
map[i][j] *= -1;
}
}
}
int[] start = new int[N+M];
int[] end = new int[N+M];
prev_diff = new int[N+M];
prev_water = new int[N+M];
XY = new int[N+M][2];
for(int i=0; i<N; i++) {
start[M+N-1-i] = 1;
end[i] = 1;
}
int min = Integer.MAX_VALUE;
while(true) {
min = check(start, temp, min);
if(Arrays.equals(start, end)) break;
update(temp, start);
}
System.out.println("Case #"+(test_case+1));
System.out.println(min);
}
}
}
코드 설명
지도를 입력받을 때 음수인 경우에 생수가 있다는 것을 저장하고 양수화 시켜서 저장하였다.
길을 탐색할 때 위로 올라가는 것보다 오른쪽을 먼저가는 것을 우선시해서 탐색했다.
그리고 check함수에서는 생수가 있는 경우 생수 개수를 ++해주고 만약 저장되어있는 최소 고도차이보다 커지게 되면 그 다음 수많은 경로들을 모두 계산할 필요없기 때문에 start배열을 바꿔주고 함수를 return한다. ( 여기서 시간 엄청 줄였는데 왜 시간 초과 나는지 아직도 모르겠따……….)
생수의 개수를 만족하는 경우 min에 고도 차이의 합을 넣는다.
start배열이 end배열과 같을 때까지 계속 배열을 update한다.