경찰차 - 사건처리 최소 거리

1. 소스 코드

문제해결을 위한 창의적 알고리즘(중급) 예제 문제, 복습 목적

하위 트리 전개는 사건을 기준으로 한다. 경찰차 위치가 하나의 처리된 사건으로 가정하고 다음 사건을 정의하는 부분을 주의 깊게 보자

#include <iostream> #include <tuple> #include <array> const int N = 3; int min = 0x7FFFFFFF; std::array< std::tuple<int, int>, N+2> accident = {{ {1, 1}, {6, 6}, {3, 5}, {5, 5}, {2, 3} }}; int distance(int a, int b) { int dx = std::abs( std::get<0>(accident[a]) - std::get<0>(accident[b]) ); int dy = std::abs( std::get<1>(accident[a]) - std::get<1>(accident[b]) ); return dx+dy; } void f(int a, int b, int s) { int next = ((a > b) ? a : b) + 1; //std::printf("a = %d b = %d next = %d s = %d\n", a, b, next, s); if(next >= N+2) { if(min > s) { min = s; } return; } f(next, b, s+distance(a, next)); f(a, next, s+distance(b, next)); } int main() { f(0, 1, 0); std::printf("min = %d \n", min); return 0; }