연휴 때 이동하면서 네비게이션 조작 많이들 하셨을 것이다. 그럴 때마다 느끼는 것이지만, 막히든 막히지 않든 길 찾아가는 그 자체가 참 신기하다.

아래의 자료를 이용해 최단거리를 구하려 한다. 단, 모든 지점은 서로 연결되어 있으며, 각 지점을 반드시 한번씩만 거쳐가야 한다.

처음엔 그래프 이론을 참고해 행렬로 어떻게 해볼려고 했으나... 예나 지금이나 행렬은 내겐 두려움의 대상이란걸 다시금 느꼈다(-_-;;). 그래서 효율은 떨어지지만 모든 순열을 이용하게 됐다. 위 조건은 아마 가장 쉬운 조건일 것이다. 조건이 조금만 달라져도 상당히 복잡해진다.

다시... 구성수가 7개이므로 필요로 하는 경우의 수는 Fact(7) = 5040건이다. 이에 지난번에 살펴본 반복없는 순열 만들기를 이용해 순열을 구축한다.

 

B2 셀:
=SMALL(IF(COUNTIF($A2:A2,{1;2;3;4;5;6;7})=0,{1;2;3;4;5;6;7}),ROUNDUP((MOD(ROW($A1)-1,FACT(COUNTA($L$2:$L$8)+1-COLUMN(A$1)))+1)/FACT(COUNTA($L$2:$L$8)-COLUMN(A$1)),0))

별다른 말이 없다면 오늘은 모두 배열수식이다. 그럼 각 지점을 한번씩 다녀가는 최단거리는...

L14 셀:
=MIN(MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))

L15 셀:
=SUM(N(MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})=MIN(MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))))

가장 짧은 이동거리는 구했는데, 어딜 어떤 순서로 가는지가 관심사일 것이다.

 

L17 셀:
=INDEX($L$2:$L$8,OFFSET(B$1,SMALL(IF(MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})=MIN(MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})),ROW($B$2:$G$5041)-ROW($A$1)),ROW($A1)),0))

S27 셀:
=SMALL(IF(MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})=MIN(MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})),ROW($B$2:$G$5041)),ROW($A1))

이 결과, 강릉 또는 광주에서 출발해야 된다. 그러나 이는 현재 위치와는 관계 없이 첫 지점으로 이동해야 한다는 얘기가 되는데... 부자연스럽다. 그래서 출발지점을 지정했을 경우를 가정하면,

 

엑셀의 함수 중첩 사용 제한 때문에 보기는 그렇긴 하나 결과를 두 줄로 나타냈다(이름 정의 하면 한 줄로 만들겠지만 귀차니즘이...).

L25 셀:
=MIN(IF($B$2:$B$5041=MATCH($L$24,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})))

L26 셀:
=SUM(N(IF($B$2:$B$5041=MATCH($L$24,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))=MIN(IF($B$2:$B$5041=MATCH($L$24,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})))))

L28 셀:
=OFFSET(B$1,SMALL(IF(IF($B$2:$B$5041=MATCH($L$24,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))=MIN(IF($B$2:$B$5041=MATCH($L$24,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))),ROW($B$2:$G$5041)-ROW($A$1)),ROW(A$1)),0)

L29 셀:
=INDEX($L$2:$L$8,L28) ← 이건 배열 수식이 아니다

S28 셀:
=SMALL(IF(IF($B$2:$B$5041=MATCH($L$24,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))=MIN(IF($B$2:$B$5041=MATCH($L$24,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))),ROW($B$2:$G$5041)),ROW(A$1))

그리고 출발한 후 가장 먼저 도착할 위치가 지정되어 있다면...

L35 셀:
=MIN(IF($B$2:$B$5041=MATCH($L$33,$L$2:$L$8,0),IF($C$2:$C$5041=MATCH($L$34,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))))

L36 셀:
=SUM(N(IF($B$2:$B$5041=MATCH($L$33,$L$2:$L$8,0),IF($C$2:$C$5041=MATCH($L$34,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1})))=MIN(IF($B$2:$B$5041=MATCH($L$33,$L$2:$L$8,0),IF($C$2:$C$5041=MATCH($L$34,$L$2:$L$8,0),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))))))

L38 셀:
=OFFSET(B$1,SMALL(IF(IF(($B$2:$B$5041=MATCH($L$33,$L$2:$L$8,0))*($C$2:$C$5041=MATCH($L$34,$L$2:$L$8,0)),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))=MIN(IF(($B$2:$B$5041=MATCH($L$33,$L$2:$L$8,0))*($C$2:$C$5041=MATCH($L$34,$L$2:$L$8,0)),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))),ROW($B$2:$G$5041)-ROW($A$1)),ROW($A1)),0)

S38 셀:
=SMALL(IF(IF(($B$2:$B$5041=MATCH($L$33,$L$2:$L$8,0))*($C$2:$C$5041=MATCH($L$34,$L$2:$L$8,0)),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))=MIN(IF(($B$2:$B$5041=MATCH($L$33,$L$2:$L$8,0))*($C$2:$C$5041=MATCH($L$34,$L$2:$L$8,0)),MMULT(N(OFFSET($L$1,$B$2:$G$5041,$C$2:$H$5041)),{1;1;1;1;1;1}))),ROW($B$2:$G$5041)),ROW($A1))

위 수식 구조를 참고하면 다른 조건에도 사용할 수 있다(예를 들어 최종 도착 위치가 지정되어 있을 때).

 

파이어폭스를 사용하는 난, 저 긴 수식을 볼 수 없다. 그리고 엑셀이 계산하는데도 시간이 아주 조금 걸린다. 이를 피하려면 셀에 이동 거리 값을 박아놓고 하는게 이후 처리가 수월하다.

I2 셀:
=SUMPRODUCT(N(OFFSET($L$1,$B2:$G2,$C2:$H2)))

그리고 자동필터 기능을 이용하면 된다.

"지금도 기억하고 있어요. 시이~월의 마지막 밤을..."

오늘은 가는 데마다 이 노래를 듣게되는군요. 10월 마무리 잘 하세요.