8. 적 비행기 회피 및 폭파로 최대 코인 모으기 알고리즘 (재귀 및 DP)

1. 개요

문제의 개요는 2차원 맵안에 배치된 적 비행기를 회피하거나 또는 

주어진 딱 한 개의 폭탄을 절묘히 사용하여 맵 안에 배치된 코인을 모으는 것이다.

풀이는 두 가지 방식으로 풀었다. 재귀와 동적 프로그래밍.

훌륭한 아이디어, 생각도 좋지만 역시나 프로그래밍의 시작은 컴퓨터답게 모든 경우를 다 검사하는 로직부터

이를 순식간에 처리하는 메모이제이션이나 DP로의 진화가 가장 좋은듯하다.

이 방법들이 통하지 않았을 경우, 그 때 훌륭한 아이디어와 생각을 적용해도 늦지않다.

일단은 모든 경우를 다 따지고보자.

총 맵은 8 X 16 크기로 예시로 설정했으며, 적 비행기가 코인을 감싸고 있는 형태로 작성하였다.

재귀 버젼에서 어떻게든 메모이제이션을 활용해보고 싶었는데, 방법이 떠오르지 않아서

동적 프로그래밍(DP)으로 풀어냈다.

재귀 방식은 모든 경우를 다 따지는 방법으로 위 예시에선 하나의 테스트케이스 당 0.5초쯤 소요된다.

즉, 수 십개의 테스트 케이스를 처리하기엔 문제가 많다.

하지만 진화된 DP 방식으로는 약 0.001초쯤 소요된다. 

 

2. 문제

비행기가 적 비행기를 피하고, 코인을 최대로 먹을 수 있는 경우를 찾아라.

조건은 적 비행기를 만나면 - 1 감소(0에서 적비행기 만나면 종료), 코인을 먹으면 + 1.

폭탄은 한 번 쓸 수 있으며, 사용할 경우 비행기 위치에서 위로 5칸 정도의 비행기는 제거.

움직이는 것은, 한번에 좌, 우, 제자리 그리고 y는 자동적으로 한칸씩 전진할 때, 

최대로 코인을 먹을 수 있는 코인의 개수는?

(예시 데이터 1)

(예시 데이터 2)

빨간색은 저 부분의 적 비행기를 부수어야만 최대 코인을 먹을 수 있다. 

미사일은 유도탄으로 앞에 장애물이 있다해도 무조건 현재 위치에서 위로 +5만큼 위치에 있는 비행기를 파괴한다.

3. 코드

데이터 입력 부분과 초기화 부분은 올리지 않음 (무척이나 난잡함)

핵심만 작성.

3-1) 재귀 코드

3-2) 재귀 출력 (모든 경우 다 따지므로 코드는 깔끔하지만 시간 소요 대폭 증가)

3-3) DP코드 1 (폭탄 사용으로 인한 추가 처리 과정 - DP 코드 2를 호출하는 과정)

3-4) DP코드 2 (진짜 Dynamic Programming이 적용된 부분)

3-5) DP 출력 1 (예시 1번)

3-6) DP 출력 2 (예시 2번)

4. 정리

이 예제를 통해 2차원 맵에서 DP가 움직이는 방식을 제대로 이해하게 되었다.

항상 직관적으로 보이는 재귀 코드가 마음에 들었는데, 성능을 고려하면 DP 방식도 무척 훌륭한 것을 알았다.

물론 코드적인 부분은 재귀가 훨씬 보기 쉽지만, DP 방식의 속도는 정말 어마어마하다.

최종 목표는 언제나 DP처럼 빠르고, 재귀처럼 간결하게.