통계로 세상보기 :: 더하기를 하자

더하기를 하자 - 여섯번째

Program 2008년 09월 19일 11시

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

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

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

다시...
구성수가 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))

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