글 읽기 - 어디가 잘못인지 모르겠습니다. ㅜ.ㅜ

tongje4385 2년 전 0

어디가 잘못인지 모르겠습니다. 고수님들 도움 좀 주세요. ㅜ.ㅜ

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

int N, M, V;
typedef struct{
    int s, e;
}DATA;

DATA data[10000+10];

int visit[10000+10];
int queue[10000*1000];
int visitq[10000+10];
int wp, rp;

int map[1000+10][1000+10];


void inputdata()
{
    scanf("%d %d %d", &N, &M, &V);
    for(int i=0; i<M; i++)
    {
        scanf("%d %d", &data[i].s, &data[i].e);
    }
}

void inqueue(int s)
{
    queue[wp++]=s;
}

int dequeue()
{
    printf("%d ", queue[rp]);
    return queue[rp++];
}

int isempty()
{
    return rp==wp;
}

void BFS()
{
    inqueue(V);
    visitq[V]=1;

    while(!isempty())
    {
        int cur=dequeue();

        for(int i=1;i<=N;i++)
        {
            if(map[cur][i]==1 && visitq[i]==0)
            {
                inqueue(i);
                visitq[i]=1;
            }
        }
    }
}

void DFS(int v)
{
    printf("%d ", v);
    visit[v]=1;

    for(int i=1;i<=N;i++)
    {
        if(map[v][i]==1 && visit[i]==0)
        {
            visit[i]=1;
            DFS(i);
        }
    }
}


int comp(const void* a, const void* b)
{
    DATA *x=(DATA*)a;
    DATA *y=(DATA*)b;

    int temp=x->s - y->s;

    if(temp==0)
        temp=x->e - y->e;

    return temp;
}

int main()
{
    inputdata();
    //qsort(data, M, sizeof(data[0]), comp);

    for(int i=0;i<M;i++)
    {
        map[data[i].s][data[i].e]=map[data[i].e][data[i].s]=1;
    }

    DFS(V);
    printf("\n");
    BFS();
    return 0;
}

dldyddlwl 2년 전 0

/*
반례

3 3 1
3 2
2 1
1 3


*/

// 기댓값 : 1 2 3
// 글쓴이님 코드 : 1 3 2

tongje4385 2년 전 0

문제를 제가 잘못이해 한건가요? 알려주신 힌트는 DFS, BFS 인지 질문 드립니다.

dldyddlwl 2년 전 0

아, dfs bfs 둘 다 저렇게 나옵니다. 한번 직접 넣어보세요.

문제에서 "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고", 라는 조건 때문에 그렇습니다.

3번과 2번이 이어져 있고

1번과 2번이 이어져 있고

1번이 3번과 이어져 있습니다.

이 때 1번에서 출발하면, 1번은 2번과 3번의 연결이 있습니다. 이 때, 정점 번호가 작은 2번을 먼저 방문해야 합니다. 1->2->3

tongje4385 2년 전 0

힌트 주신대로 양방향인것을 다시 생각해보고

2차원 배열로 생각해 보니 쉽게 풀렸네요. 감사합니다.

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

문제

문제

출처

ICPC

어디가 잘못인지 모르겠습니다. ㅜ.ㅜ

tongje4385 2년 전 0

dldyddlwl 2년 전 0

tongje4385 2년 전 0

dldyddlwl 2년 전 0

tongje4385 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말