글 읽기 - 어떤 논리가 틀렸을까요 ?

johyesong8686 4년 전 0

어떤 논리가 틀린지 모르겠습니다 ㅜㅜ

1.정점을 입력받는다. ==>이때 queue에하나씩 넣어줌

2.queue에서 하나씩 정점을 꺼내서 bfs가 가능하면 연결요소 갯수 num을 늘려줌

==>연결 요소가 여러개 인 경우에 횟수를 확인하게 위해서 많일 같은 연결요소에 속해있다면

bfs를 통해 이미 방문 되었을 것이고 횟수에 포함되지 않는다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector <int> a[49501];
vector <int> node[1001];
bool c[1001] = { 0, };

//bfs진행 bfs가 가능하면 true 출력 
bool bfs(int start) {
	queue <int> q;
	if(!c[start]){
			q.push(start);
	c[start]=true;
	while(!q.empty()){
		
		int x =q.front();
		q.pop();
		//printf("%d \n",x);
		for(int i=0;i<a[x].size(); i++){
			int y=a[x][i];
			//printf("a[%d][%d]; :%d \n",x,i,a[x][i]);
			//printf("size :%d \n",a[x].size());
			if(!c[y]){ //방문을 안한 상태이면 
				
				q.push(y);
				c[y]=true;
			}
				
		}
		
	}
	return true;
	}
	return false;

	

}

int main(void) {
	int N, M;
	int num=0;
	queue <int> node;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
        //서로 연결 된 정점 vector에 대입
		node.push(x);
		node.push(y);
        //queue에 입력 받은 정점 대입
		
	}
    //입력받은 정점이 bfs가 가능한지 확인
	while(!node.empty()){
        
			int start=node.front();
			node.pop();
        
			if(bfs(start)){
              //가능하다면 num을 늘려줌
			num++;		
				}	
	}
	
	printf("%d",num);


}

catenary 4년 전 1

node 큐에 정점을 입력하는 53 54번째 줄이 문제입니다.

존재하는 모든 정점에 대해 각각 한번씩 bfs를 돌려 확인하는게 맞는데, 주어진 연결 요소들에 대해서만 모두 bfs를 돌리고 있어요.

이 예시입력같은 경우 node 큐에

1,2,2,5,5,1,3,4,4,6 가 다 들어가있어요.

불필요하게 bfs를 돌리는것도 문제지만

3 1

1 2

이런 입력같은 경우, node 큐에 1과 2만 들어가있기때문에 3정점에 대해 bfs 를 돌리지 못해 정답은2지만 출력이 1로 나오고 있어요.

johyesong8686 4년 전 0

간선 N이 1~N의 정점이라는 생각을 못했네요 ! ㅜㅜ

정점만 있고 간선은 아예 업는 경우도 포함된다는 생각을 못했던것같아요

문제

문제

출처

ICPC

어떤 논리가 틀렸을까요 ?

johyesong8686 4년 전 0

catenary 4년 전 1

johyesong8686 4년 전 0

y_w2700 3년 전 0

catenary

감사합니다

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말