1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <stdlib.h>
 
typedef struct a {
    int vert; struct a *link;
}node;
node *makeList(int , node *);
int bfs(int, int, node **, int);
void enqueue(node **, node *, int *);
int main() {
    int vert, edge, m,n,i;
    scanf("%d%d%d%d", &vert, &m, &n, &edge);
    node **adjList=(node**)calloc(vert+1, sizeof(node*));
    for (i=1; i<=vert; i++) {
        adjList[i]=(node*)calloc(1, sizeof(node));
        adjList[i]->vert=i;
    }
    while(edge--) {
        int u, v;
        scanf("%d%d", &u, &v);
        adjList[u]->link=makeList(v, adjList[u]->link);
        adjList[v]->link=makeList(u, adjList[v]->link);
    }
    printf("%d\n", bfs(m, n, adjList, vert));
 
}
 
node *makeList(int u, node *list) {
    node *new=calloc(1, sizeof(node)), *p=list, *q=list;
    new->vert=u;
    if(list==NULL) {
        list=new;
        return list;
    }
    while(p!=NULL) {
        if(p->vert>u) break;
        q=p;
        p=p->link;
    }
    if (p==list) {
        list->link=new;
    }
    else {
        q->link=new;
    }
    new->link=p;
    return list;
}
 
int bfs(int search, int target, node **list, int vert) {
    int count=0, *visited=(int*)calloc(vert+1, sizeof(int));
    node *queue=NULL, *p=list[search];
    enqueue(&queue, p, visited);
    while(queue!=NULL) {
        int v=queue->vert;
        queue=queue->link; count++;//dequeue::== return front;
        for(p=list[v]; p; p=p->link) {
            if(visited[p->vert]==0) {
                if (p->vert == target)
                    return count;
                enqueue(&queue, p, visited);
            }
        }
    }
    return -1;
}
 
void enqueue(node **queue, node *target, int *visited) {
    node *new=(node*)calloc(1, sizeof(node)), *p=*queue;
    new->vert=target->vert;
    visited[target->vert]=1;
    if(*queue==NULL) *queue=new;
    else {
        while(p->link!=NULL) p=p->link;
        p->link=new;
    }
}
cs

boj.kr/2644
촌수 계산 문제야

학교에서 dfs/bfs 배운걸로 하고 있는데
방법 자체가 틀려서 시간 초과가 뜨는건가??