[Dynamic Programming] 로보트

 

1. 동적계획법

- 여러 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

- 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다.

 

2.  동적 계획법 VS 그리디 알고리즘

 

- 모든 가능성을 고려해야하는 동적 계획법과 달리 최적해 (경로)를 구하여 문제를 푸는 방법으로 비교적 효율적인 알고리즘으로 본다.

 

예) 최단거리 로보트 이동

 

로보트가 위치한 방향에서 Goal을 향하는 경로룰 구하는 방법을 출력하는 문제로 상하좌우 모든 방향의 경로 이동을 시도해야하는 동적계획법 알고리즘 문제이다.

 

위 그림을 다음과 같이 행렬로 구현한다.

        boolean[][] grid = 
        {
                {false, false, false, false},
                {false, false, false, true},
                {true, true, false, false},
                {false, false, false, false}
      	};

 

문제를 해결하기 위해 3가지 클라스로 나누어 해결해보자

1. ArrayList<> findPath

 

위 배열에서 로보트가 이동하는 경로 알고리즘으로 클라스 내부의 2. "boolean findPath" 클라스에서 에서 true / false 를 확인하여 경로 이동이 가능한지 확인한다.

 

3.  isInRange

배열 내부에서 알고리즘이 작동하도록 범위를 제한해야한다. 범위를 벗어난 경우 false를 반환한다.