글 읽기 - 채점 50%에서 자꾸 틀리네요 ㅠㅠ 도와주세요

craclog 7년 전 1

혼자 해결해보려다 결국 질문합니다..ㅠ

어떤 질문글에 정점(n)의개수가 1000개 이하일 뿐, n이 1~1000 이 아니라는 글을 본거같아서

이렇게 짯습니다. 혹시 무조건 1~n 까지라 가정해도 되는건가요?

예제와 주석처리해놓은 값들도 제대로 나옵니다. 어떤 Test case에서 틀리는지 모르겠네요ㅠ

#include <stdio.h>
#define SWAP(x,y) { int t; (t) = (x); (x) = (y); (y) = (t); }
/*
Example
8 10 1
1 2 1 3 2 4 2 5 4 8 5 8 3 6 3 7 6 8 7 8

DFS : 1 2 4 8 5 6 3 7
BFS : 1 2 3 4 5 6 7 8
==========================================
6 8 1
1 6 6 2 2 4 4 3 3 5 5 1 5 6 2 3

DFS : 1 5 3 2 4 6
BFS : 1 5 6 3 2 4
*/
// n is not 1~1000
// n is Interger!
int start[20001] = {0};
int end[20001] = {0};
int queue[1001] = {0};
int visited[1001] = {0};
int m;

void DFS(int v){
    int i;
    visited[v] = 1;
    
    for(i=0; i<2*m; i++){
        if(start[i] == v && visited[end[i]] != 1){
            printf(" %d",end[i]);
            DFS(end[i]);
        }
    }
}
void BFS(int v){
    int i;
    int head = 0;
    int tail = -1;
    visited[v] = 1;
    printf("%d",v);   
    do{
        for(i=0; i<2*m; i++)
            if(start[i] == v && visited[end[i]] != 1){
                tail++;
                queue[tail] = end[i];
                visited[end[i]] = 1;
                printf(" %d",end[i]);
            }
        v = queue[head];
        head++;
    }while(head <= tail);
    
}

int main(){
    int i,j,n,v;
    int tmp1,tmp2;
    
    scanf("%d%d%d",&n,&m,&v);
    //양방향이므로 Array를 2배로 하고 양쪽으로 넣음
    for(i=0; i<m; i++){
        scanf("%d%d",&tmp1,&tmp2);
        start[i] = tmp1;
        start[m+i] = tmp2;
        end[i] = tmp2;
        end[m+i] = tmp1;
    }
   
    //오름차순으로 정렬 start[] & end[]
    for(i=0; i<2*m-1; i++){
        for(j=i+1; j<2*m; j++){
            if(start[i] > start[j]){
                SWAP(start[i],start[j]);
                SWAP(end[i],end[j]);
            }
            else if(start[i] == start[j])
                if(end[i] > end[j]){
                    SWAP(start[i],start[j]);
                    SWAP(end[i],end[j]);
                }
            
        }
    }
    //출력
    printf("%d",v);
    DFS(v);
    puts("");
    //initializing
    for(i=0; i<1001; i++)
        visited[i] = 0;
        
    BFS(v);
    puts("");
    
    
    return 0;
}

sgchoi5 7년 전 1

저도 하수라 어디가 문제인지는 모르겠네요 제가 푼거보니 너무 복잡하게 푸신것 같아서....

#define MAX 1000
int map[MAX + 1][MAX + 1];
int visited[MAX + 1];

int queue[MAX*MAX + 1];

정점을 연결하는 간선정보를 2차원 배열로 처리할 수 있습니다 (1000정도는 가능)

for (int m = 0; m < M; m++) {
scanf("%d %d", &v1, &v2);
map[v2][v1] = map[v1][v2] = 1; // 양방향
}
이렇게 하고 다음 찾을때 1부터 MAX 값순으로 검색하면 따로 소트할필요도 없습니다...

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

문제

문제

출처

ICPC

채점 50%에서 자꾸 틀리네요 ㅠㅠ 도와주세요

craclog 7년 전 1

sgchoi5 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말