글 읽기 - C언어 시간초과 질문 있습니다.

joonbo97 3년 전 0

코드를 작성하여 보든 정점에 대해 탐색을 하고, 각정점에는 색깔정보를 저장하여, 이미 색칠이 된 정점일때, 같은 색이 나오는 경우 멈추도록 하였습니다.

시간초과를 해결할 방안을 모르겠습니다.

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

typedef struct _Veretex {//정점
    int color;
}vertex;

typedef struct _Edge {//간선
    int start;
    int end;
}edge;

int main() {
    int T, N, M, state, cnt;
    scanf("%d", &T);

    for (int t = 0; t < T; t++)
    {
        scanf("%d%d", &N, &M);
        vertex* V = (vertex*)malloc(sizeof(vertex) * (N + 1));
        edge* E = (edge*)malloc(sizeof(edge) * M);
        
        for (int i = 0; i < M; i++)
            scanf("%d %d", &E[i].start, &E[i].end);

        for (int i = 1; i <= N; i++)
            V[i].color = 0;

        state = 0;
        int vertex_num;

        V[1].color = 1;
        vertex_num = 1;//탐색할 정점
        int color_value = 2;//색칠해야되는 색 (1과 2)

        cnt = 1;//몇개의 점의 색을 변경하였는지..
        while(cnt < N)
        {
            for (int i = 0; i < M; i++)//M개의 정점들중 우리가 원하는 점에 대한 값이 있는 경우 확인
            {
                if (E[i].start == vertex_num)
                {
                    if (V[E[i].end].color == 0)
                    {
                        V[E[i].end].color = color_value;
                        cnt++;
                        vertex_num = E[i].end;
                        if (color_value == 2)
                            color_value = 1;
                        else
                            color_value = 2;
                    }
                    else if (V[E[i].end].color != color_value)
                    {
                        state = 1;
                    }

                }
                else if (E[i].end == vertex_num)
                {
                    if (V[E[i].start].color == 0)
                    {
                        V[E[i].start].color = color_value;
                        cnt++;
                        vertex_num = E[i].start;
                        if (color_value == 2)
                            color_value = 1;
                        else
                            color_value = 2;
                    }
                    else if (V[E[i].start].color != color_value)
                    {
                        state = 1;
                    }
                }
                if (state == 1)
                    break;
            }
            if (state == 1)
                break;
        }

        if (state == 0)
            printf("YES\n");
        else
            printf("NO\n");


        free(V);
        free(E);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C언어 시간초과 질문 있습니다.

joonbo97 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말