Java | 재귀적 알고리즘 연습, N x N maze 경로 상 최대값

🎇 재귀적 알고리즘

• 장점

관계중심으로 파악하여 문제를 간명하게 볼 수 있다. 
명확한 의미 전달과 간결한 프로그램 작성이 가능하다.

• 단점

재귀적 방법을 사용하면 심한 중복 호출이 일어날 수 있다.

• 재귀적 프로그램을 만드는 방법

1. 재귀적 구조 (최적 부분 구조 : Optimal Substructure)을 찾는다.
2. 적어도 하나 이상의 base case를 찾는다.
3. 수렴하는지 확인한다. 
4. 자신을 호출할 때 매개변수를 암시적(ex:public static 변수)이 아니라,
   명시적 parameter로 표시해야 한다. 

---

문제

N x N maze에서, 경로 상 숫자들을 합할 때 최대값을 구해라.
미로의 좌 상단에서 시작해서 한 칸씩 이동하여 우 하단에 도달한다.

규칙

1. 오른쪽 혹은 아래로만 이동이 가능하다.
2. 왼쪽, 윗쪽, 대각선 이동은 허용하지 않는다. 

접근

오른쪽 하단 4를 ( i , j )라고 해보자.
이곳에 도달하기 직전에 방문할 수 있는 곳은 ( i , j-1)과 ( i-1, j), 2곳이 있다.

1) ( i-1, j ) 거쳐서 ( i, j )에 도달하는 경우

2) ( i , j-1 ) 거쳐서 ( i, j )에 도달하는 경우

중에서 합이 높은 쪽을 택하면 된다.

Sum( i , j )

(1) maze[i][j] (i=0,j=0)     
(2) maze[i][j] + Sum(i,j-1) (i=0)
(3) maze[i][j] + Sum(i-1,j) (j=0)
(4) maze[i][j] + Max(Sum(i,j-1), Sum(i-1,j)) (else)   

구현

public class Maxsum {
	int count = 0;

	int[][] maze;

	public Maxsum(int[][] in) {
		maze = in;
	}

	public int findMax(int i, int j) {
		count++;
		if (i == 0 && j == 0)
			return maze[i][j];
		if (i == 0)
			return maze[i][j] + findMax(i, j - 1);
		if (j == 0)
			return maze[i][j] + findMax(i - 1, j);
		return maze[i][j] + Math.max(findMax(i, j - 1), Math.max(findMax(i - 1, j), findMax(i - 1, j)));
	}

	public int getCount() {
		return count;
	}

	public static void main(String[] args) {
		int[][] maze = { { 1, 2, 1, 5, 8, 4 }, { 4, 1, 9, 4, 2, 3 }, { 8, 5, 4, 3, 8, 2 }, { 1, 5, 3, 5, 7, 3 },
				{ 4, 7, 7, 9, 2, 8 }, { 2, 4, 6, 3, 1, 4 } };

		Maxsum me = new Maxsum(maze); // maze를 전달하는 Maxsum 인스턴트 생성

		System.out.println("Maxsum = " + me.findMax(maze.length - 1, maze.length - 1) + "  count = " + me.getCount());

	}

}