정렬 거리 편집하기 (부분)

=== 백트래킹 ===
하지만 최종 매트릭스만 가지고 어떤 선택의 결과가 "4"인지 알기는 어렵다. 이를 위해선 우리가 구한 최종 값, 즉 마지막 행 마지막 열에 있는 "4"를 시작점으로 역추적(백트래킹)이 필요하다. 백트래킹 규칙은 아래와 같다:

#마지막 값이었던 "4"를 만들게 된 그 칸으로 따라간다.
#예를 들어 대각선에서 1이 더해지거나 빼진 것이 "4"인지, 위 또는 왼쪽에서 2가 더해진 것이 "4"인지 파악한다.
#*만약 두 값이 같다면 이 둘 다 답이다.
#이렇게 해당되는 것을 표시하며 올라가다 보면 첫 칸에 닿게 된다. 이 때 표시된 지점들이 답이 될 수 있는 지점이다.
#*2번에서 설명했듯이 값이 둘다 해당사항이 있다면 그건 여러 갈레로 갈라지는 것이다. 이 각 갈레들을 추적하면 여러개의 답을 모두 구할 수 있다.
먼저 하나의 경로만 추적해보자.

* 아래는 대각선으로 갈 수 있으면 대각선으로 가고, 대각선으로 갈 수 없는 경우엔 왼쪽으로 가고, 왼쪽으로도 갈 수 없으면 위쪽으로 가는 규칙으로 만들어진 경로이다.
* dp[6][7]의 (4)는 대각선 위에 있는 dp[5][6]의 = (5)에서 1이 빼진 값이다. 물론 왼쪽 dp[6][6]의 (2)에서 2가 더해진 값일 수도 있지만 여기선 해당 경로는 잠시 제쳐두겠다.
* 그 다음 dp[5][6]의 (5)는 dp[4][5]의 (4)에서 1이 더해진 값이다.
* 그 다음 dp[4][5]의 (4)는 dp[3][4]의 (4)에서 온 값이 아니다. 대각선을 기반으로 하려면 1이 더해지거나 빼져야 하는데 값이 같기 때문이다. 왼쪽 dp[3][3]의 (2)에서 2가 더해진 값일 수 있다.

이렇게 추적해나가다 보면 하나의 길이 그려진다. 이 과정에서 보았듯 여러 갈레의 길이 있었다. 각각의 다른 갈레가 나올 때 마다 다른 답이 나오는 것이다. 우선 이 경로를 어떻게 해석하는지 살펴보자. 첫번째 (0)은 제외하고 글자가 있는 칸부터 순서대로 선택해서 대응되는 글자들을 적어준다.

* f - * (행엔 f가 있는데 열엔 값이 없다. 아래위 방향이므로 f가 삽입된 경우이다.)
* i - i (동일한 값이 매칭된 경우이다.)
* n - n (동일한 값이 매칭된 경우이다.)
* * - f (좌우 방향이므로 f가 삭제된 경우이다.)
* * - i (좌우 방향이므로 i가 삭제된 경우이다.)
* a - l (대각선 방향으므로 치환된 경우이다.)
* l - l (대각선 방향이므로 치환된 경우이다.

결국 아래와 같다.
 *  i  n  f  i  l  l 
 f  i  n  *  *  a  l
 2 -1 -1  2  2  1 -1 = 4

{| class="wikitable"
!
!
!i
!n
!f
!i
!l
!l
|-
!
|'''(0)'''
|2
|4
|6
|8
|10
|12
|-
!f
|'''(2)'''
|1
|3
|3
|5
|7
|9
|-
!i
|4
|'''(1)'''
|2
|4
|2
|4
|6
|-
!n
|6
|3
|'''(0)'''
|'''(2)'''
|'''(4)'''
|3
|5
|-
!a
|8
|5
|2
|1
|3
|'''(5)'''
|4
|-
!l
|10
|7
|6
|3
|2
|2
|'''(4)'''
|}