[문제해결을 위한 창의적 알고리즘] 경찰차 2 (고급, p170)

앞선 포스트에서 가장 쉬운 완전탐색 방법으로 해결하는 코드를 소개한 적이 있다. 이 방법보다 보다 효율적인 방법으로 메모이제이션을 활용한 코드를 소개하고자 한다.

import java.util.Scanner;

public class PatrolCarSol174 {

public static int[][] E = new int[1010][2];

public static int n, m, ans =987654321;

public static int[][] DT=new int[1100][1100];

public static int min(int a, int b){

return a > b ? b : a;

}

public static int abs(int a){

return a > 0? a:-a;

}

public static int dis(int a, int b){

return abs(E[a][0]-E[b][0])+abs(E[a][1]-E[b][1]);

}

public static int f(int a, int b){

if (DT[a][b]==0){

int next = (a > b? a : b)+1;

if (next > m+1)

DT[a][b]=0;

else

DT[a][b]=min(f(next, b)+dis(a, next), f(a, next)+dis(b, next));

}

return DT[a][b];

}

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

m = sc.nextInt();

E[0][0]=E[0][1]=1;

E[1][0]=E[1][1]=n;

for (int i =2; i < m+2; i++){

E[i][0]=sc.nextInt();

E[i][1]=sc.nextInt();

}

sc.close();

System.out.println(f(0,1));

/*

for (int i = 0; i<m+2; i++)

System.out.println(DT[i][0]+" "+DT[i][1]);

*/

return;

}

}

Big O(m)

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/PatrolCarSol174.java

문제해결을 위한 창의적 알고리즘 목록

출처: 한국정보올림피아드 (2003 전국본선 중등부)