백준 11048 자바 - 이동하기 (BOJ 11048 JAVA)

https://www.acmicpc.net/problem/11048

 

  만약 이동이 상하좌우로 가능했었다면, 혹은 [우측, 아래, 우측아래, 좌측]과 같이 좌측으로도 이동이 가능했다던지 하면 BFS 등의 방법으로 전체 경우를 보면서 풀어야 한다. 하지만 이처럼 방향이 우측, 아래, 우측아래 대각선 처럼 한쪽 '사분면'으로 고정되어 있다면 Dynamic Programming(DP; 동적계획법)으로 더 간단하게 풀 수 있다.

 

  일단 다음의 그림을 보자.

위 그림은 이 문제에서 (1,1)에서 (N,M)으로 갈 때 각 위치에서 이동할 수 있는 방향을 나타낸 것이다.

그럼 위 그림에서 예를들어 정중앙의 '5'로 올 수 있는 화살표만 남겨보겠다.

다음으로 중앙 우측의 '6'으로 오는 화살표이다.

그럼 벽에 붙어있는 '2'이나 '9' 같은 지점은 어떨까?

화살표는 똑같이 생각해도 된다. 다만 없는 위치라면 그냥 무시하면 된다.

 

  그럼 여기서 뭘 알 수 있냐면, N이라는 지점으로 들어오는 3가지 방향의 데이터가 모두 확정되어서 이후 더 바뀔 가능성이 아예 없다면, N지점에서 N으로 들어오는 3가지 방향 중 한 곳을 아무곳이나 선택해도 상관이 없다는 점이다. 이 문제에서는 최대치의 사탕개수를 구하면 되므로 N지점으로 들어오는 3가지 방향 중 가장 사탕개수가 많은 곳에서 N지점으로 왔다고 생각하면 되는것이다.

 

  처음에 한쪽 사분면으로만 진행된다면 BFS같은게 아니라 DP로 풀 수 있다고 한 이유가 이건데, 이 문제의 경우, 단순히 배열을 좌측에서 우측으로, 위에서 아래로 순회한다고 보자. 그럼 어느지점에 오든지 자신의 좌측상단, 좌측, 위의 데이터는 이미 확정된 상태가 된다. 이처럼 한쪽 사분면으로만 이동할 수 있다면 그 이전값들을 고정시키고 다음위치로 갈 수 있게된다. 그럼 위에서 예시를 들었던 이미지를 기준으로 전체 과정을 봐보자.

 

1. 시작지점에서는 딱히 할 일이 없다. 우측으로 진행하자!

2. '2'가 써져있던 지점에 왔다. 자신의 위는 아무것도 없다. 좌측위도 없다. '2'로 올 수 있는 지점은 좌측인 시작지점 뿐이다. 따라서 좌측에서 온 경우를 선택했고, 현재까지의 사탕갯수는 2+1 이다. 다시 우측으로!

3. 마찬가지로 위와 좌측위에선 못오므로 좌측에서만 올 수 있다. 따라서 3+3으로 변경된다. 이번엔 아래줄의 처음지점인 '4'가 써져있는 위치로 가자!

4. 이번엔 좌측과 좌측위에서 올 수 없으므로, 마찬가지로 위에서만 올 수 있다. 따라서 4+1로 변경된다.

5. 이번엔 올 수 있는 지점이 위, 좌측위, 좌측 모두 가능하다! 지금까지 잘 보면, 어떠한 지점에 왔을 때 항상 자신의 좌측, 좌측위, 위쪽은 이미 확정된 최대값이라 더이상 바뀔 가능성이 없다는 점을 알 수 있다. 이번에도 마찬가지다. 그럼 3가지 중 값이 가장 큰 방향에서 왔다고 치면 현재지점까지의 최대 사탕개수를 구할 수 있다. 이 경우 좌측에서 오면 된다.

6. 이후 나머지 모든 경우를 별도의 설명 없이 쭉 그려보겠다.

7. 그럼 최종적으로 구하고자 하는 사탕의 최대 개수는 29가 되고, 지나온 길은 아래와 같다.

 

 

  그럼 이제 이걸 코드로 구현하면 된다. 사실 입력도 row 단위로 주어지므로, 미리 입력받을 필요도 없이 계속 입력받으면서 자신의 좌측위, 위, 좌측의 값 중 최대값을 구하면 된다.(15line) 이런식의 문제의 경우 약간의 팁으로, 미리 배열 크기를 좌측과 위에 한칸씩 늘려놓자. 그럼 시작지점 부터도 동일한 코드로 구현이 가능하다. 12line에서 늘려놨음. 만약 new int[n][m]; 을 했다면 15line 부분에서 바로 저렇게 3개를 넣지 못하고, 위나 좌측이나 좌측위가 존재하지 않는 경우 분기를 나눠서 처리해야 한다. (귀찮다.) 메모리를 약간 손해보고 코딩의 편함을 취한거임.

 

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11000/BOJ_11048.java