글 읽기 - DFS 와 BFS 인접리스트 방식으로 구현했는데 틀린부분을 못찾겠습니다.

sgc109 8년 전 0

이 문제를 처음에 인접 행렬방식으로 짜서 맞았는데 실행시간이 4ms 라 0ms 로 만들어 보고자

인접 리스트 방식으로 다시구현을 해봤습니다.. 그런데 제가 테스트한 경우들에 대해서는 모두 같은 결과가 나왔는데

제출을 했더니 틀렸다고 나왔습니다.. 어떤부분이 잘못된건지 찾을수가없는데 도와주시면 감사드리겠습니다..

#define REP(i,a,b) for(int i = a; i < b;++i)
#define FOR(i,n) REP(i,0,n)

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stack> 
#include<queue>
#include<string.h>


using namespace std;

int N,M,V;
vector<vector<int>> adj;
vector<int> visited;
queue<int> q;
vector<int> discovered;

void bfs(int start) {
    discovered[start] = 1;
    q.push(start);
    int cur_nod;
    while(!q.empty()) {
        cur_nod = q.front();
        q.pop();
        printf("%d ",cur_nod+1);
        FOR(i,adj[cur_nod].size()) {
            if(!discovered[adj[cur_nod][i]]) {
                discovered[adj[cur_nod][i]] = 1;
                q.push(adj[cur_nod][i]);
            }
        }
    }
}

void dfs(int here) {
    printf("%d ",here+1);
    visited[here] = 1;
    FOR(there,adj[here].size()) {
        if(!visited[adj[here][there]]) dfs(adj[here][there]);
    }
}

int main() {
    scanf("%d %d %d",&N,&M,&V);
    adj = vector<vector<int>>(N);
    visited = vector<int>(N,0);
    discovered = vector<int>(N,0);
    
    FOR(i,M) {
        int a,b;
        scanf("%d %d",&a,&b);
        --a;
        --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    dfs(V-1);    
    printf("\n");
    bfs(V-1);
    
    return 0;
}

sgc109 8년 전 0

@cubelover 아... 저런조건이붙었다면 리스트로 할때는 정렬을 해주어야하는군요!! 감사합니다!!

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

문제

문제

출처

ICPC

DFS 와 BFS 인접리스트 방식으로 구현했는데 틀린부분을 못찾겠습니다.

sgc109 8년 전 0

sgc109 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말