[C언어] 2606번 바이러스 - 인접 그래프, BFS

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 101

int cnt;

typedef struct GraphType {
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

void init(GraphType *g)
{
    int r, c;
    g->n=0;
    for(r=0; r<MAX_VERTICES; r++)
        for(c=0; c<MAX_VERTICES; c++)
            g->adj_mat[r][c]=0;
}

void insert_edge(GraphType *g, int start, int end)
{
    g->adj_mat[start][end]=1;
    g->adj_mat[end][start]=1;
}

void cnt_vertex(int u, GraphType *g)
{
    int i, j;
    
    for(i=1; i<=g->n; i++) {
        if(g->adj_mat[u][i]) {
            for(j=1; j<=g->n; j++)
                g->adj_mat[j][i]=0;
            g->adj_mat[u][i]=0, g->adj_mat[i][u]=0;
            cnt_vertex(i, g);
        }
    }
    cnt++;
}

int main()
{
    int M;  //컴퓨터 쌍의 수
    int u, v;  //연결되는 컴퓨터 번호;
    int i, j;
    GraphType *g;
    
    g=(GraphType *)malloc(sizeof(GraphType));  //인접 그래프 구현
    init(g);
    
    scanf("%d %d", &g->n, &M); g->n;
    for(i=0; i<M; i++) {
        scanf("%d %d", &u, &v);
        insert_edge(g, u, v);  //그래프 삽입
    }
    for(i=1; i<=g->n; i++)
        g->adj_mat[i][1]=0;
    cnt_vertex(1, g);
    
    printf("%d", cnt-1);
    
    return 0;
}

 

그래프로 플어야 한다고 한다. 물론 나는 그래프를 몰랐기 때문에 다른 블로그에서 공부를 했다. 참고한 블로그 주소는 아래에 있다. 인접 그래프로 N*N 그래프로 만들어서 노트에 표 그래면서 알고리즘 자니까 빨리 끝났다. 

 

 

<인접 그래프>

https://velog.io/@kysung95/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-C%EB%A1%9C-%EA%B7%B8%EB%9E%98%ED%94%84%EB%A5%BC-%EB%A7%8C%EB%93%A4%EC%9E%90

[자료구조론] C로 그래프를 만들자

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.