글 읽기 - c++ bfs로 짰는데 질문좀요

xron2929 2년 전 0

질문 창에서 반례를 찾으려고 해도 보이지 않아 질문드립니다

위 코드는 1을 Q에 넣고, 1이랑 연결된 지점들을 Q에 넣을 때마다, unf 배열안에 Q의 앞부분 값을 넣어주고, 1부터 n까지 탐색해 unf[i]가 0이아니라면, 1씩 더해주고, 마지막으로, 1일 때 -1로 빼주는 코드입니다

양방향도 해주었고, 배열도 너무 작을까봐 늘렸는데도 14%작동하지 않네요...

예외 데이터가 있을까요?

#include<bits/stdc++.h>
using namespace std;
int graph[1001][1001],res[1001],mmax=0,unf[1001],ccnt;
int n,m,a,b;

int main()
{
	freopen("input.txt","rt",stdin);
	queue<int>Q;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		graph[a][b]=1;
		graph[b][a]=1;
	}
	Q.push(1);
	while(!Q.empty())
	{
		int now=Q.front();
		Q.pop();
		unf[now]=now;
		for(int i=1;i<=n;i++)
		{
			if(graph[now][i]==1)
			{
				graph[now][i]=0;
				Q.push(i);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(unf[i]!=0)
		{	
			mmax++;
		}
	}
	cout<<mmax-1; 
}

midascha 2년 전 0

아래의 코드로 변경해서 제출을 해 봤습니다. 통과하네요.

변경한 부분은

1. pc댓수는 100여서 array자릿수를 1001 -> 101로 변경.

2. 혹시라도 unf array에 이상한 값이 있을수도 있어서 초기화를 다음과 같이 했습니다. fill_n(unf, 101, 0);

3. 소소한 수정은 #include 부분을 제 pc 환경에 맞게 수정했습니다.

아래의 코드를 참조해 보세요. 참고로 저는 DFS로 풀었습니다. 그래프 문제는 BFS보다 DFS가 더 효율적이 않을까 개인적인 의견입니다.

감사합니다

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
int graph[101][101], mmax = 0, unf[101], ccnt;
int n, m, a, b;

int main()
{
	queue<int>Q;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	fill_n(unf, 101, 0);

	Q.push(1);
	while (!Q.empty())
	{
		int now = Q.front();
		Q.pop();
		unf[now] = now;
		for (int i = 1; i <= n; i++)
		{
			if (graph[now][i] == 1)
			{
				graph[now][i] = 0;
				Q.push(i);
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (unf[i] != 0)
		{
			mmax++;
		}
	}
	cout << mmax - 1;
}

xron2929 2년 전 0

감사합니다

관련 답변으로 문제점을 파악하였습니다 :)

두번째로는 c언어 memset을 사용했는데, c++에도 fill_n이라는 초기화 라이브러리가 존재한다는 사실을 알게되었네요

도움주셔서 감사합니다

혹시 모르는 분들이 있으실 까 답변을 드리자면, 원인은 freopen으로 파일 선언을 해줘서 문제가 된 것 같습니다..

다른 사이트에선 문제가 나타나지 않았는데 아마 그곳에서는 freopen이 자동으로 헤체되어서 오류가 나지 않았던것으로 추측됩니다..

마지막으로 글쓴이 분에게 감사의 말씀을 드립니다

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

문제

문제

출처

ICPC

c++ bfs로 짰는데 질문좀요

xron2929 2년 전 0

midascha 2년 전 0

xron2929 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말