최소비용신장트리도 가볍게 풀어 버린 우리 아이들...

다음과 같은 문제가 있습니다.

여기서 모든 번호를 최소의 비용으로 연결 하라는 문제입니다.

데이터는  다음과 같이 들어 오구요...

5

0 5 10 8 7 

5 0 5 3 6 

10 5 0 1 3 

8 3 1 0 1 

7 6 3 1 0

정답은 10이 나와야 합니다.

1 - 2 연결시 5

2 - 4 연결시 3

4 - 3 연결시 1

4 - 5 연결시 1

의 비용이 발생해서 10의 비용이 나오는 문제 입니다.

저 이 문제 알고리즘 찾아 내는데 굉장히 힘들어 했던것으로 기억합니다.

그런데 우리 아이들... 이런 문제는 아주 쉽게 풀어 버리네요.^^

이 문제의 핵심은

1번에서 출발해서 비용이 가장 작은 2번으로 가는 것입니다.

그리고 나서 1번은 방문했다고 마킹을 하는것이죠.

그 다음 1번에서 갈수 있는 비용과 2번에서 갈수 있는 비용 중 가장 작은 2번에서 4번으로 3의 비용으로 가는 것입니다.

마지막으로 4번에서 5번과 3번으로 1씩의 비용으로 찾아간다는 머 그런 내용입니다.

이게 크루스칼 알고리즘인데요...

그냥 사람이 눈으로 보면 굉장히 빨리 단순하게 계산되는데...(이런거 보면 정말 사람의 두뇌는 엄청난거 같아요^^)

이걸 로직화 해서 작업 하는게 쉽지는 않더라구요...

물론 위의 크루스칼 알고리즘 이해하는데도 저 같은 경우는 한참 걸렸거든요...^^

제가 놀랐던 아이의 소스 코드입니다.

#include<stdio.h>   int cost[100][100]; int p[100];   int GetMin(int N) {     int i,j,total=0,m=100000,madd;       for(i=0;i<N;i++) p[i]=cost[0][i];       while(1)     {         for(j=0;j<N;j++)         {             if(p[j] && m>p[j]) m=p[j], madd=j;         }         if(!madd) break;         total+=m;         for(j=0;j<N;j++)         {             p[j]=(p[j]<cost[madd][j]) ? p[j]:cost[madd][j];         }         m=100000, madd=0;     }       return total; }   int main() {     //freopen("input.txt","r",stdin);       int N,i,j;       scanf("%d",&N);     for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d",&cost[i][j]);       printf("%d \n",GetMin(N)); }

참 간결하게 잘 짜 놓았네요...

저 보다도 소스가 훨씬 간결하고도 이쁘게 짜 놓았습니다.

for(i=0;i<N;i++) p[i]=cost[0][i];




p 라는 배열을 하나 두고 처음에 0번위치에서 갈수 있는곳의 비용을 모두 담았네요.

for(j=0;j<N;j++)

        {

            if(p[j] && m>p[j]) m=p[j], madd=j;

        }




그중에서 가장 작은 값을 m에 madd 에는 그 위치를 담았구요...

if(!madd) break;




갈곳이 없으면 그만 수행하도록 했네요.




for(j=0;j<N;j++)

        {

            p[j]=(p[j]<cost[madd][j]) ? p[j]:cost[madd][j];

        }




그리고 여기에서는 그 다음 가야하는 위치(madd) 를 돌아 보면서 p 배열을 작은 값으로 갱신을 하네요...

p 배열에 처음에는 0 5 10 8 7 을 넣어 두고 m=5, madd = 1 이 되니까...

1번째 위치의 5 0 5 3 6 을 p배열로 작은 값을 갱신 하니까 p 배열 값에는 0 0 5 3 6 이 되겠네요.

방문한 위치를 0 값을 가지고 확인 했구요.^^

이문제에 직면해서 해법을 잘 찾지 못할때...

크루스칼 알고리즘을 설명 들어 가는데...

설명 해 주기도 전에 이렇게 풀어 버린 아이에게 크루스칼 알고리즘을 설명 해 주어야 하는걸까요?

지금 이아이가 찾아낸 알고리즘에 그냥 이름만 붙인건데요...

(이렇게 실제로 찾아낸 알고리즘을 대학교에 가서 학문으로 배우게 되면 아이의 흡수력은 어떨까요?

사실 대학교에서는 이렇게 알고리즘을 배워도 이걸 충분히 활용하기에는 시간적인 한계가 있기도 합니다. 하지만 이렇게 이미 터득한 학생들은 대학에서 배우는 학문으로 몇단계 점프를 할것입니다.) 

저희 학원에서는 아이들이 스스로 문제를 풀어가는 학습법으로 진행 합니다.

이렇게 풀어가는 학습법의 장점은...

아이들 스스로 생각 하게 하고 새로운 문제를 접했을때 누구한테 의지 하려고 하지 않고 스스로 어떤 문제를 해결 할 수 있다는 것이거든요.

우리 아이들 모두 화이팅! 을 조그맣게 외쳐 보는 주말이네요.^^