글 읽기 - DFS BFS 어떤 것이 틀렸을까요?

dohyeokkim 8년 전 0

adjacency list로 만들었고 작은 node부터 방문해야 하므로 min heap을 썼습니다.

똑같은 graph를 2개나 만든 이유는,

queue가 iterator가 없어서 계속 pop을 하는 식으로 구현했기 때문에 dfs가 끝나면 graph가 다 날아가서...

(혹시 이게 문제가 될까요? 어차피 한 번 고려 되면 나중에 이 edge는 절대 쓸 일이 없으니 pop해도 된다고 생각했는데요.)

아니면 혹시 출력 형식이 이상한 걸까요?

(그런데 이런 경우는 틀렸습니다가 아니고 출력 형식이 이상하다고 채점이 되긴 하던데...)

#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

vector<priority_queue<int, vector<int>, greater<int>>> G1; 
vector<priority_queue<int, vector<int>, greater<int>>> G2; 
vector<int> visited;

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

  while (!G1[v].empty()){
    int candi = G1[v].top();
    G1[v].pop();
    if (!visited[candi]){
      dfs(candi);
    }   
  }

  return;
}

void bfs(int s){ 
  queue<int> Q;
  Q.push(s);
  visited[s] = 1;

  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    printf("%d ", v); 

    while (!G2[v].empty()){
      int candi = G2[v].top();   
      G2[v].pop();
      if (!visited[candi]){
        Q.push(candi);
        visited[candi] = 1;
      }
    }   
  }

  return;
}

int main(){
  int n, m, v;

  scanf("%d %d %d", &n, &m, &v);
  G1.clear();
  G1.resize(n + 1);
  G2.clear();
  G2.resize(n + 1);
  visited.clear();
  visited.resize(n + 1);

  for(int i = 0; i < m; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    G1[a].push(b);
    G2[a].push(b);
  }

  dfs(v);

  puts("");
  visited.clear();
  visited.resize(n + 1);

  bfs(v);

  return 0;
}

dohyeokkim 8년 전 0

이 문제 또한 sh0416님이 local하게 해결해주셨습니다.

undirected graph인 걸 모르고 adjacency list를 만들 때 한 방향만 넣어줬네요 ㅠㅠ

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

문제

문제

출처

ICPC

DFS BFS 어떤 것이 틀렸을까요?

dohyeokkim 8년 전 0

dohyeokkim 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말