[기본과정, 3단계]

3-1-1.n!-순환알고리즘

#include<stdio.h>
int f(int p)
{
    if(p==1) return 1;
    
    int u;
    u = p*f(p-1);
    return u;
}
int main()
{
    int n,k;
    
    scanf("%d",&n);
    k=f(n);
    printf("k=%d\n",k);
    
    return 0;
} 

3-1-2.n!-비순환알고리즘

#include<iostream>
using namespace std;
int s[1004];

int main()
{
	int sp=0,n,nn;

	cin >> n;
	nn=n;
	while(1){
		sp++; s[sp]=nn;
		if(nn==1)break;
		nn--;
	}
	while(1){
		nn=s[sp]; sp--;
		s[sp]*=nn;
		if(sp==1)break;
	}
	cout << s[sp];

	return 0;

}




3-2-1.피보나치수열-순환알고리즘

#include<stdio.h>
int f(int p)
{
    if(p==1 || p==2) return 1;
    return f(p-1)+f(p-2);
}
int main()
{
    int n,k ;
    
    scanf("%d",&n);
    k=f(n);
    printf("%d\n",k);
    
    return 0;
}

3-2-2.피보나치수열-비순환알고리즘
#include<iostream>
using namespace std;
int s[1004], d[1004]; 
int main()
{
	int n,nn,sp=0,np;

	cin >> n;
	d[1]=1; d[2]=1; nn=n;
	while(1)
	{
		sp++; s[sp]=nn;
		if(d[nn]!=0)break;
		nn--;
	}
	while(1)
	{
		nn=s[sp]; sp--; 
		if(sp==0)break;
		np=nn-1;
		d[s[sp]]=d[nn]+d[np];
	}
	cout << d[nn];

	return 0;
}




3-3.2진수 구하기-순환알고리즘

#include<stdio.h>
int f(int p)
{
    if(p==0) return 0;
    f(p/2);
    printf("%d",p%2);
    return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    f(n);
    printf("\n");
    return 0;
}



3-4-1.2진트리-순환알고리즘

#include<stdio.h>
int n;
int f(int p)
{
    if(p>n) return 0;

    f(p*2);
    printf("%d ",p);
    f(p*2+1);
    return 0;
}
int main()
{
    scanf("%d",&n);
    f(1);
    printf("\n");
    return 0;
}


3-4-2.2진트리-비순환알고리즘

2진트리 전위
#include<iostream>
using namespace std;
int s[1004];
int main()
{
	int n,sp=0,nl,nr;

	cin >> n;
	sp++; s[sp]=1;
	while(1){
		cout << s[sp] << " ";
		nl=s[sp]*2; nr=s[sp]*2+1; sp--;
		if(nr<=n){sp++; s[sp]=nr;}
		if(nl<=n){sp++; s[sp]=nl;}
		if(sp==0)break;
	}
	cout << endl;
	return 0;
}

2진트리 중위
#include<iostream>
#include<memory.h>
using namespace std;
int s[1004]; bool d[1004];
int main()
{
	int n,sp=0,nl,nr; 

	cin >> n;
	sp++; s[sp]=1;
	memset(d,0,sizeof(d));
	while(1){
		if(d[s[sp]]==0){
			nl=s[sp]*2; d[s[sp]]=1;
			if(nl <= n){
				sp++; s[sp]=nl;
			}
		}else{
			cout << s[sp] << " ";
			nr=s[sp]*2+1; sp--;
			if(nr<=n){
				sp++; s[sp]=nr;
			}
		}
		if(sp==0)break;
	}
	
	return 0;
}

2진트리 후위
#include<iostream>
using namespace std;
int s[1004]; bool d[1004];
int main()
{
	int n,sp=0,a,nl;

	cin >> n;
	sp++; s[sp]=1;
	while(1){
		if(d[s[sp]]==0){
			nl=s[sp]*2; d[s[sp]]=1;
			if(nl<=n){sp++; s[sp]=nl;}
			else {
				cout << s[sp] << " "; 
				a=s[sp]; sp--;
				if(a%2==0){
					if(a+1<=n){sp++; s[sp]=a+1;}
				}
			}
		}
		else {
			cout << s[sp] << " "; 
			a=s[sp]; sp--;
			if(a%2==0){
				if(a+1<=n){sp++; s[sp]=a+1;}
			}
		}
		if(sp==0)break;
	}
	
	return 0;
}




3-4-3.2진 트리 깊이(특강추가)
(intput)
1 2 4 7 -1 -1 8 -1 -1 -1 3 5 -1 -1 6 -1 -1
(output)
4 1 3
4

#include<stdio.h>
int count[3],ans;

int dfs(int d)
{
	int v,cnt=0;
	
	scanf("%d",&v);
	if(v==-1) return 0;
	if(ans < d) ans = d;
	cnt += dfs(d+1);
	cnt += dfs(d+1);
	++count[cnt];
	
	return 1;	
}

int main()
{
	dfs(1);
	for(int i=0; i<3; i++)printf("%d ",count[i]);
	printf("\n%d\n",ans);
	
	return 0;
}



3-4-4.2진 트리-순환알고리즘k(특강추가)
(intput)
1 2 4 7 -1 -1 8 -1 -1 -1 3 5 -1 -1 6 -1 -1
(output)
-1 7 -1 4 -1 8 -1 2 -1 1 -1 5 -1 3 -1 6 -1
-1 -1 7 -1 -1 8 4 -1 2 -1 -1 5 -1 -1 6 3 1


#include<stdio.h>
int N, num[1004], left[1004], right[1004];

int dfs()
{
	int v;
	
	scanf("%d", &v);
	if(v==-1) return 0;
	int n=++N, k;
	num[n]=v;
	if(k=dfs()) left[n]=k;
	if(k=dfs()) right[n]= k;
	
	return n;
}

int in(int n)
{
	if(!n){printf("-1 ");return 0;}
	in(left[n]);
	printf("%d ",num[n]);
	in(right[n]);
	
	return 0;
}

int pos(int n)
{
	if(!n){printf("-1 ");return 0;}
	pos(left[n]);
	pos(right[n]);
	printf("%d ",num[n]);
	return 0;
}

int main()
{
	dfs();
	in(1); puts("");
	pos(1); puts("");
	return 0;
}



3-4-5. 무한 이진 트리(특강추가)
(intput)
17 73
(output)
4 6

#include<stdio.h>
int L,R;

int f(int a, int b)
{
	if(a==1 && b == 1) return 0;
	if(a == 1){
		R += b-1;
		return 0;
	}
	if(b==1){
		L += a-1;
		return 0;
	}
	if(a > b){
		L += a/b;
		f(a%b, b);
	}
	if(a < b){
		R += b/a;
		f(a, b%a);
	}
}

int main()
{
	int a,b;
	
	scanf("%d %d",&a, &b);
	f(a,b);
	printf("%d %d\n",L,R);
	
	return 0;
}



3-5.하노이탑-순환알고리즘

#include<stdio.h>
int f(int p, int s, int e)
{
    int k;
    if(p<=0) return 0;
    
    k=6-(s+e);
    f(p-1,s,k);
    printf("%d %d %d\n",p,s,e);
    f(p-1,k,e);
    
    return 0;
}
int main()
{
    int n;
    
    scanf("%d",&n);
    f(n,1,3);
    
    return 0;
}



3-6-1. 부분 집합(순환알고리즘)

#include<stdio.h>
int n,d[100],z[100];
int f(int p, int s)
{
    int i;
    
    if(p==n+1){
        printf("{");
        for(i=1; i<=n; i++){
            if(z[i]==1) printf("%d ",d[i]);
        }
        printf("}=%d\n",s);
        return 0;
    }
    z[p]=0;    f(p+1, s);
    z[p]=1;    f(p+1, s+d[p]);
    return 0;
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        scanf("%d",&d[i]);
    }
    f(1,0);
    return 0;
} 



3-6-2. 부분 집합(비순환알고리즘, 특강추가)

#include<stdio.h>
int d[1004];
int z[1004][1004];
int main()
{
    int n,i,j,c,cc,k;
    
    scanf("%d",&n);
    for(i=1; i<=n; i++)scanf("%d",&d[i]);
    z[1][1]=0; c=1; z[1][0]=1;
    for(i=1; i<=n; i++){
        cc=c;
        for(j=1; j<=c; j++){
            cc++;
            for(k=1; k<=z[j][0]; k++){
                z[cc][k] =z[j][k];
            }
            z[cc][k]=d[i];
            z[cc][0]=k;
        }
        c=cc;
    }
    
    for(i=2; i<=cc; i++){
        for(j=2; j<=z[i][0]; j++)    printf("%d ",z[i][j]);
        printf("\n");
    }
    
    return 0;
}



3-7-1. 미로 찾기-dfs(순환)

#include<stdio.h>
#include<stdlib.h>
int d[101][101],n, dx[101], dy[101];
int f(int x, int y, int p)
{
    int i;
    
    if(x==n && y==n){
        dx[p]=x; dy[p]=y;
        for(i=1; i<=p; i++) printf("%d %d\n",dx[i], dy[i]);
        printf("ok!\n");
        return 0;
    }
    if(d[x][y]==1){
        dx[p]=x; dy[p]=y;
        d[x][y]=0;
        f(x-1, y, p+1);
        f(x, y-1, p+1);
        f(x+1, y, p+1);
        f(x, y+1, p+1);
        d[x][y]=1;
    }
    
    return 0;
}
int main()
{
    int i,j;
    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            scanf("%d",&d[i][j]);
        }
    }
    f(1,1,0);
    return 0;
}



3-7-2. 미로 찾기-bfs(비순환, 특강추가)

#include<stdio.h>
struct data{
    int x,y,p;
};
int z[1001][1001],px[1001], py[1001];
int main()
{
    int i, j, n, sp=0, zx, zy, zp;
    
    struct data s[1004];
    freopen("input.txt","r",stdin);
    
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            scanf("%d",&z[i][j]);
        }
    }
    
    sp=1; s[sp].x=1; s[sp].y=1; s[sp].p=1;
    while(sp!=0){
        zx=s[sp].x; zy=s[sp].y;zp=s[sp].p;sp--;    z[zx][zy]=0;
        px[zp]=zx; py[zp]=zy;
        if(zx==n && zy==n) break;
        if(z[zx-1][zy]==1){sp++; s[sp].x=zx-1; s[sp].y=zy; s[sp].p=zp+1;}
        if(z[zx][zy-1]==1){sp++; s[sp].x=zx; s[sp].y=zy-1; s[sp].p=zp+1;}
        if(z[zx+1][zy]==1){sp++; s[sp].x=zx+1; s[sp].y=zy; s[sp].p=zp+1;}
        if(z[zx][zy+1]==1){sp++; s[sp].x=zx; s[sp].y=zy+1; s[sp].p=zp+1;}
    }
    for(i=1; i<=zp; i++) printf("%d %d\n",px[i],py[i]);
    
    return 0;
}



3-8-1. 중복 순열-dfs

#include<stdio.h>
int n,m,d[101];
int f(int p, int q)
{
    int i,j;
    
    if(q>=m){
        for(j=1; j<=m; j++)printf("%d ",d[j]);
        printf("\n");
        return 0;
    }
    for(i=1; i<=n; i++){
        d[q+1]=i;
        f(i,q+1);
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n, &m);
    f(0,0);
    return 0;
}



3-8-2. 중복 순열(비순환, 특강추가)-bfs

#include<stdio.h>
int a[100004], b[100004], c[100004], z[100],s[1004];
int main()
{
    int n,m,f,t,ff,i;
    scanf("%d %ds",&n, &m);
    
    f=1; t=1; ff=0;
    while(1)
    {
        for(i=1; i<=n; i++){
            a[++t]=i;
            b[t]=f;
            c[t]=c[f]+1;
            z[c[t]]=t;
            if(c[t]>m){ ff=1; break;}
        }
        f++;
        if(ff==1)break;
    }
//    for(i=1; i<t; i++) printf("%d %d %d\n",a[i], b[i], c[i]);
    
    int zz, sp, j, ii;
    zz=z[m-1]+1;
    for(i=zz; i<=z[m]; i++){
        sp=0; ii=i;
        while(1)
        {
            sp++; s[sp]=a[ii];
            ii=b[ii];
            if(b[ii]==0) break;
        }
        for(j=sp; j>=1; j--)printf("%d",s[j]);
        printf("\n");
    }

    return 0;
}



3-9. 순열-dfs

#include<stdio.h>
int n,m,d[101],z[101];
int f(int p, int q)
{
    int i,j;
    
    if(q>=m){
        for(j=1; j<=m; j++)printf("%d ",d[j]);
        printf("\n");
        return 0;
    }
    for(i=1; i<=n; i++){
        if(z[i]==0){
            z[i]=1;
            d[q+1]=i; f(i,q+1);
            z[i]=0;
        }
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n, &m);
    f(0,0);
    return 0;
}



3-10. 조합-dfs

#include<stdio.h>
int n,m,d[101];
int f(int p, int q)
{
    int i,j;
    
    if(q>=m){
        for(j=1; j<=m; j++)printf("%d ",d[j]);
        printf("\n");
        return 0;
    }
    for(i=p+1; i<=n; i++){
        d[q+1]=i; f(i,q+1);
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n, &m);
    f(0,0);
    return 0;
}



3-10-1. 월드컵(2008년도 KOI전국본선 중등부 1번)(특강추가)

(1단계 소스)

#include<stdio.h>
#include<conio.h>

#define n 6
#define m 15

int w[n], l[n], d[n], gw[n], gl[n], gd[n];
int g[m], p1[m], p2[m];
bool ff;

int recur( int cnt )
{
	int i, j;

	if (cnt == m){
		for(j=0; j<n; j++){
			printf("%d: %d %d %d\n",j, gw[j], gd[j], gl[j]);
		}
		printf("\n");
		getch();
		return 0;
	}
	
	gw[p1[cnt]++;gl[p2[cnt]++;
	recur(cnt+1);
	gw[p1[cnt]--;gl[p2[cnt]--;
	
	gd[p1[cnt]]++;gd[p2[cnt]]++;
	recur(cnt+1);
	gd[p1[cnt]]--;gd[p2[cnt]]--;
	
	gl[p1[cnt]]++;gw[p2[cnt]]++;
	recur(cnt+1);
	gl[p1[cnt]]--;gw[p2[cnt]]--;
	
	return 0;
}

int process()
{
	int i, j, cnt = 0;
	
	for (i=0; i<n; i++){
		gw[i] = 0; gl[i] = 0; gd[i] = 0;
		if (w[i]+l[i]+d[i] != n-1) return 0;
	}
	
	for (i=0; i<n; i++){
		for (j=i+1; j<n; j++){
			p1[cnt] = i;
			p2[cnt] = j;
			cnt++;	
		}
	}
	recur(0);
	return 0;
}

int main()
{
	freopen("input.txt","r",stdin);
	
	for (int i = 0; i<1; i++){
		for (int j=0; j<n; j++) scanf("%d %d %d",&w[j], &d[j], &l[j]);
		process();
	}
	
	return 0;
}

(2단계 소스)

#include<stdio.h>
#include<conio.h>

#define n 6
#define m 15

int w[n], l[n], d[n], gw[n], gl[n], gd[n];
int g[m], p1[m], p2[m];
bool ff;

int recur( int cnt )
{
	if (cnt == m){
		for(int j=0; j<n; j++){
			printf("%d: %d %d %d\n",j, gw[j], gd[j], gl[j]);
		}
		printf("\n");
		getch();
		
		ff = 1;
		return 0;
	}
	int n1 = p1[cnt], n2 = p2[cnt];
	
	gw[n1]++; gl[n2]++; 
	if (gw[n1]<=w[n1] && gl[n2]<=l[n2]) recur(cnt+1);
	gw[n1]--; gl[n2]--;
	
	gd[n1]++; gd[n2]++; 
	if (gd[n1]<=d[n1] && gd[n2]<=d[n2]) recur(cnt+1);
	gd[n1]--; gd[n2]--;
  
	gl[n1]++; gw[n2]++; 
	if (gl[n1]<=l[n1] && gw[n2]<=w[n2]) recur(cnt+1);
	gl[n1]--; gw[n2]--;

	return 0;
}

int process()
{
	int i, j, cnt = 0;
	
	ff = 0;
	for (i=0; i<n; i++){
		gw[i] = 0; gl[i] = 0; gd[i] = 0;
		if (w[i]+l[i]+d[i] != n-1) return 0;
	}
	for (i=0; i<n; i++){
		for (j=i+1; j<n; j++){
			p1[cnt] = i;
			p2[cnt] = j;
			cnt++;
		}
	}
	recur(0);
	
	return 0;
}

int main()
{
	freopen("input.txt","r",stdin);
	
	for (int i = 0; i<1; i++)
	{
		for (int j=0; j<n; j++) scanf("%d %d %d",&w[j], &d[j], &l[j]);
		process();
		if (ff==1) printf("1 ");
		else printf("0 ");
	}
	
	return 0;
}




3-10-2. 장난감 조립(2000년도 KOI전국본선 중등부 1번)(특강추가)

(프로그램)

#include<stdio.h>
int a[101][101], b[101], c[101], n, m;

void Go(int p, int v)
{
	int q, i;
	
	b[p] += v;
	for(q=1; q<=n; q++){
		if(a[p][q])Go(q, v * a[p][q]);
	}
}

int main(void)
{
	int i, j, t1, t2;

	freopen("input.txt","r",stdin);

	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&t1, &t2);
		c[t1] = 1;
		scanf("%d",&a[t1][t2]);
	}
	Go(n, 1);
	for(i=1;i<=n;i++){
		if(c[i] == 0) printf("%d %d\n",i,b[i]);
	}

	return 0;
}



3-10-3. 퀵정렬-1단계 분할 정복(특강추가)

(프로그램)
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int d[100];
int f(int s, int e)
{
    int ss,ee,t;
    
    if(s>=e) return 0;
    while(1)
    {
        ss=s+1; ee=e;
        while(d[s]>=d[ss] && ss <= e)ss++;
        while(d[s]<=d[ee] && ee > s)ee--;
        if(ss>=ee)break;
        t=d[ss]; d[ss]=d[ee]; d[ee]=t;
    }
    t=d[s]; d[s]=d[ee];d[ee]=t;
    f(s, ee-1);
    f(ee+1, e);   
   
    return 0;
}
int main()
{
    int i,n;
    srand(time(0));

    scanf("%d",&n);
    for(i=1; i<=n; i++){
        d[i]=rand()%100;
    }

    for(i=1; i<=n; i++)printf("%d ",d[i]);   
    printf("\n\n");
   
    f(1,n);

    for(i=1; i<=n; i++)printf("%d ",d[i]);   
    printf("\n");

    return 0;
}



3-10-4. 색종이 만들기-2단계 분할 정복(특강추가)

(2001년도 KOI전국본선 중등부 1번)

(프로그램)
#include<stdio.h>

int a[200][200];
int blue, white;

int f(int x, int y, int p)
{
	int b=0, w=0,i,j;
	
	for (i=x;i<x+p;i++){
		for (j=y;j<y+p;j++){
			if (a[i][j]==1) b++; 
			else w++;
		}
	}
	if (b==0) {white++; return 0;}
	if (w==0) {blue++; return 0;}
	f(x, y, p/2);
	f(x, y+p/2, p/2);
	f(x+p/2, y, p/2);
	f(x+p/2, y+p/2, p/2);
	
	return 0;
}

int main()
{
	int n,i,j;

	scanf("%d",&n);
	for (i=0;i<n;i++){
		for (j=0;j<n;j++){
			scanf("%d",&a[i][j]);
		}
	}

	f(0,0,n);

	printf("%d\n", white);
	printf("%d\n", blue);
	
	return 0;
}



3-10-5. 여왕문제(특강추가)

(프로그램)
#include<stdio.h>

int qq[100];
int n;
int bound(int pp)
{
    int i;
    for(i=1; i<pp; i++){
        if(qq[pp] == qq[i]) return 0;
        if(pp+qq[pp] == i+qq[i]) return 0;
        if(pp-qq[pp] == i-qq[i]) return 0;
    }
    return 1;
}
int q(int p)
{
    int i, k;
    if(p>n){
        for(k=1; k<=n; k++) printf("(%d %d)", k, qq[k]);
        printf("\n");
        return 0;
    }
    for(i=1; i<=n; i++){
        qq[p]=i;
        if(bound(p)) q(p+1);
    }
    return 0;
}
int main()
{
    scanf("%d", &n);
    q(1);
   
    return 0;
}



3-11-1. 모든쌍의 최단경로(특강추가, 순환)
(input)
6 4
0 1 50
0 2 10
2 1 20
1 2 15
2 3 15
3 1 20

(output)
0 2 3 1 45
0 2 10
0 2 3 25
1 2 0 35
12 15
1 2 3 30
2 0 20
2 3 1 35
2 3 15
3 1 2 0 55
3 1 20
3 1 2 35

(1단계)
#include<stdio.h>
int d[1004][1004];
int n,k;
int main()
{
	int a,b,c,i,j;
	
	freopen("input.txt","r",stdin);
	scanf("%d %d",&n, &k);
	for(i=1; i<=n; i++){
		scanf("%d %d %d",&a, &b, &c);
		d[a][b]=c;
	}
	
	for(i=0; i<k; i++){
		for(j=0; j<k; j++) printf("%3d",d[i][j]);
		printf("\n");
	}
	
	return 0;
}

(2단계)
#include<stdio.h>
int d[1004][1004];
int n,k;

int main()
{
	int a,b,c,i,j;
	
	freopen("input.txt","r",stdin);
	scanf("%d %d",&n, &k);
	for(i=0; i<k; i++){
		for(j=0; j<k; j++)d[i][j]=99999;
		d[i][i]=0;
	}
	for(i=1; i<=n; i++){
		scanf("%d %d %d",&a, &b, &c);
		d[a][b]=c;
	}
	
	for(i=0; i<k; i++){
		for(j=0; j<k; j++) printf("%6d",d[i][j]);
		printf("\n");
	}
	
	return 0;
}

(3단계)
#include<stdio.h>
#include<conio.h>
int d[1004][1004],z[1004];
int n,k, g;
int f(int p, int q, int r)
{
	int i,j;
	if(q>=k || (q>0 && g==p)){
		z[q]=p;
		for(j=0; j<=q; j++) printf("%d ",z[j]);
		printf("=>%d\n",r);
		getch();
		return 0;
	}
	
	for(i=0; i<=k; i++){
		if(p!=i && d[p][i] != 99999){
			z[q]=p;
			f(i, q+1, r+d[p][i]);
			z[q]=0;
		}
	}
	return 0;
}

int main()
{
	int a,b,c,i,j;
	
	freopen("input.txt","r",stdin);
	scanf("%d %d",&n, &k);
	for(i=0; i<k; i++){
		for(j=0; j<k; j++)d[i][j]=99999;
		d[i][i]=0;
	}
	for(i=1; i<=n; i++){
		scanf("%d %d %d",&a, &b, &c);
		d[a][b]=c;
	}

	for(i=0; i<k; i++){
		g=i;
		f(i,0,0);
	}

	for(i=0; i<k; i++){
		for(j=0; j<k; j++) printf("%6d",d[i][j]);
		printf("\n");
	}
	
	return 0;
}

(4단계)
#include<stdio.h>
#include<conio.h>
int d[1004][1004],z[1004];
int n,k, g;
int f(int p, int q, int r)
{
	int i,j,rr;
	if(q>=k || (q>0 && g==p)){
		z[q]=p;
		for(j=0; j<=q; j++) printf("%d ",z[j]);
		printf("=>%d\n",r);
		return 0;
	}
	
	for(i=0; i<k; i++){
		if(p==i)continue;
		rr=r+d[p][i];
		if((rr!=0) && (rr < d[g][i]))d[g][i]=rr;
		if(d[p][i] != 99999){
			z[q]=p;
			f(i, q+1, rr);
		}
	}
	return 0;
}

int main()
{
	int a,b,c,i,j;
	
	freopen("input.txt","r",stdin);
	scanf("%d %d",&n, &k);
	for(i=0; i<k; i++){
		for(j=0; j<k; j++)d[i][j]=99999;
		d[i][i]=0;
	}
	for(i=1; i<=n; i++){
		scanf("%d %d %d",&a, &b, &c);
		d[a][b]=c;
	}
	for(i=0; i<k; i++){
		for(j=0; j<k; j++) printf("%6d",d[i][j]);
		printf("\n\n");
	}
	for(i=0; i<k; i++){
		g=i;
		f(i,0,0);
	}

	for(i=0; i<k; i++){
		for(j=0; j<k; j++) printf("%6d",d[i][j]);
		printf("\n");
	}
	
	return 0;
}

(5단계)
#include<stdio.h>
#include<conio.h>
int d[1004][1004],z[1004],m[1004];
int n,k, g;
int f(int p, int q, int r)
{
	int i,j,rr;
	if(q>=k || (q>0 && g==p)){
		z[q]=p;
		for(j=0; j<=q; j++) printf("%d ",z[j]);
		printf("=>%d\n",r);
		return 0;
	}
	
	for(i=0; i<k; i++){
		if(p==i)continue;
		if(m[i]==1)continue;
		rr=r+d[p][i];
		if((rr!=0) && (rr < d[g][i]))d[g][i]=rr;
		if(d[p][i] != 99999){
			z[q]=p;m[i]=1;
			f(i, q+1, rr);
			m[i]=0;
		}
	}
	return 0;
}

int main()
{
	int a,b,c,i,j;
	
	freopen("input.txt","r",stdin);
	scanf("%d %d",&n, &k);
	for(i=0; i<k; i++){
		for(j=0; j<k; j++)d[i][j]=99999;
		d[i][i]=0;
	}
	for(i=1; i<=n; i++){
		scanf("%d %d %d",&a, &b, &c);
		d[a][b]=c;
	}
	for(i=0; i<k; i++){
		for(j=0; j<k; j++) printf("%6d",d[i][j]);
		printf("\n\n");
	}
	for(i=0; i<k; i++){
		g=i;m[g]=1;
		f(i,0,0);
		m[g]=0;
	}

	for(i=0; i<k; i++){
		for(j=0; j<k; j++) printf("%6d",d[i][j]);
		printf("\n");
	}
	
	return 0;
}
* 이 프로그램은 확실한 오류가 있습니다. 찾아보세요!



3-11-2. 모든쌍의 최단경로(특강추가, 비순환)

#include<stdio.h>
int d[1001][1001], v[1001][1001];
int n;

int print_v(int i, int j)
{
    int k;
    k = v[i][j];
    if(v[i][k] != -1)print_v(i,k);
    printf("%d ",k);
    return -1;
}

int output()
{
    int i,j;
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if(i!=j && d[i][j] !=99999){
                printf("%d ",i);
                if(v[i][j] !=-1) print_v(i,j);
                printf("%d (%d)\n",j,d[i][j]);
            }
            else if(d[i][j]==99999)printf("%d %d impossible",i,j);
        }
        printf("\n");
    }
    return 0;
}

int main()
{
    int k,a,b,c,i,j,p;
    
    freopen("input.txt","r",stdin);
   
    scanf("%d %d",&n, &k);
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if(i!=j)d[i][j]=99999;
            v[i][j]=-1;
        }
    }
   
    for(i=0; i<k; i++){
        scanf("%d %d %d",&a,&b,&c);
        d[a][b]=c;
    }
   
    for(p=0; p<n; p++){
        for(i=0; i<n; i++){
            if(p == i)continue;
            for(j=0; j<n; j++){
                if(d[i][p]+d[p][j] < d[i][j]){
                    d[i][j]=d[i][p]+d[p][j];
                    v[i][j]=p;
                }
            }
        }
    }
   
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            printf("%6d", d[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            printf("%6d", v[i][j]);
        }
        printf("\n");
    }
   
    output();
    
    return 0;
}


* 참고, 순환알고리즘 & BT알고리즘으로 해결하는 한국정보올림피아드 전국본선 문제들 입니다.

언제가는 꼭 해결해 보기!!

제16회 한국정보올림피아드 전국본선 중등부 1번 촌수계산(BT)

제16회 한국정보올림피아드 전국본선 중등부 3번 같은 길이 막대기 만들기(BT)

제17회 한국정보올림피아드 전국본선 중등부 1번 장난감 조립(BT)

제18회 한국정보올림피아드 전국본선 중등부 1번 색종이 만들기(BT)

제22회 한국정보올림피아드 전국본선 중등부 2번 유전자(BT + 다이나믹)

제25회 한국정보올림피아드 전국본선 중등부 1번 월드컵(BT)

제27회 한국정보올림피아드 전국본선 중등부 1번 용액(BT)

등등