제일 만족하는 길찾기 문제를 재귀로 풀어보기

길찾기 알고리즘은 숫자가 적을경우는 그냥 사실 루프 몇번 돌려서 만들면 되는데, 다만 그 숫자가 굉장히 커질경우 계산이 느려질수 있다.

 

 

1 2 4 1 5 5

2 5 2 1 4 5

2 5 2 1 5 6

1 3 4 2 5 1

1 2 5 2 4 1

2 5 1 4 3 4

 

 

위와같이 6 X 6 바둑판같은 길이 있다고 하고,

1) 최소경로로 가야하며

2) 밟고 다니는 숫자의 합이 최대인 길을 찾아야 하며

3) 찾는 속도가 좀 빨라야한다.

 

 

사실 알고리즘에 있어서 기본은 재귀를 어떻게 잘 돌리냐에 따른건데, 보통사람은 동적프로그래밍을 먼저 생각해내겠지만, 알고리즘을 열심히 푸는 사람들에게는 재귀가 항상 먼저 답으로 다가오는 듯 하다.

 

위의 경우에서는 다음과 같은 경우로 길을 선택한다고 볼수있는데,

 

- 처음인경우 (즉 1 X 1 블럭인경우)

 

- 위쪽인경우 (1 X N) 이전단계와 지금 점수를 더한다

 

- 옆쪽인 경우 (N X 1) 이전단계와 지금 점수를 더한다.

 

- 아니면 그냥 보통인 경우 (N X N) 위나 옆 두칸 중 큰 숫자를 선택해서 더한다.

 

public class Path {
	
	public static void main(String[] args) {
		
		int[][] map = {{1, 2, 4, 1, 5, 5}, 
					   {2, 5, 2, 1, 4, 5},
					   {2, 5, 2, 1, 5, 6},
					   {1, 3, 4, 2, 5, 1},
					   {1, 2, 5, 2, 4, 1},
					   {2, 5, 1, 4, 3, 4}};
		
		System.out.println(sum(map, 6 - 1, 6 - 1));
		
	}//end main
	
	public static int sum(int[][] map, int x, int y) {

		if (x == 0 && y == 0)
			return map[x][y];
		else if (x == 0)
			return sum(map, x, y - 1) + map[x][y];
		else if (y == 0)
			return sum(map, x - 1, y) + map[x][y];
		else
			return max(sum(map, x - 1, y), sum(map, x, y - 1)) + map[x][y];

	}

	public static int max(int n1, int n2) {
		return (n1 > n2) ? n1 : n2;
	}

}

 

위와같은 로직으로 간단히 풀수 있다.

 

다만, 미친듯이 재귀로 돌아가니 중복계산이 발생하여 정말정말 느려지고 잘못하면 스택오버플로우가 생겨버릴 수 있다. 따라서, 동적프로그래밍으로 풀면 되는데, 이는 별건 아니고 저 배열과 같은 크기의 칸을 만들어놓고 왼쪽에서부터 가능한 점수를 더하는 방법이다.

 

이를 적고 싶으나 시간이 지금 당장 강원도를 놀러가야 하므로 다음에 적든지 하겠다.