글 읽기 - C/C++ 언어 BFS 로 했는데 시간 초과 나오네요 고수님들 부탁드립니다.

dudql92 3년 전 0

예제 답이랑 반례 답은 모두 잘나오는데

시간초과가 나오네요....

제가 비효율적으로 짠건가요 아니면 이 문제는 DFS로 풀어야 효율적인가요..

저의 코드가 PASS 될 수 있도록 조언 주시면 감사하겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;


int N,E,result;
int Graph[1001][1001];
int visit[1001][1001];

queue<int> que;

void BFS()
{
	int temp =0;
	for(int i=1; i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			if(Graph[i][j] ==1 && visit[i][j]!=1)
			{
				result ++;
				que.push(j);
				visit[i][j] =1;
			}
		}

		while(!que.empty())
		{
			temp = que.front();
			que.pop();
			for(int k =1;k<=N;k++)
			{
				if(Graph[temp][k] == 1&& visit[temp][k]!=1)
				{
					que.push(k);
					visit[temp][k] =1;
				}
				if(Graph[k][temp] == 1&& visit[k][temp]!=1)
				{
					que.push(k);
					visit[k][temp] =1;
				}	
			}
		}

	}



}


int main()
{
	int x,y =0;
	scanf("%d %d", &N,&E);

	for(int i =0; i< E;i++)
	{
		scanf("%d %d",&x,&y);

		Graph[x][y]=1;
	}


	BFS();

	for(int i=1; i<=N;i++)
	{
		
		for(int j=1; j<=N;j++)
		{
			if((Graph[i][j]==1) ||(Graph[j][i]==1))
			{
				break;
			}
			if(j==N)
			{
				result ++;
			}
		}

	}
	printf("%d \n", result);

}

sr5757 3년 전 1

우선 속도면에서는 main에서 BFS아래의 이중포문을 빼고 BFS에서 visit 체크위치를 두번째 포문 들어가기 전에 체크하면 시간초과는 받지 않을 것 같습니다.

그리고 visit 배열은 [1001][1001]일 필요가 없습니다. 방문표시를 하는 곳이 간선인지 정점인지 확인해보시면 됩니다

result++하는 위치도 다시 고민해주세요.

이 문제의 그래프는 방향이 없는 그래프이므로 입력받을때 graph[y][x]에도 1표시를 해주시면 bfs의 while문 안에서 조건체크를 한 번만 해도 됩니다.

sonjaewon 3년 전 0

아, 혹시 저도 도와주실 수 있으신가요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int co = 0;
vector<int> a[1000010];
bool visited[1000010] = { 0, };
void dfs(int node)
{
	visited[node] = true;
	for (int i = 0; i < a[node].size(); i++)
	{
		int next = a[node][i];
		if (!visited[next]) dfs(next);
	}
}

int main()
{
	int n, m;
	int x, y;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 1; i <= m; i++)
	{
		if (!visited[i])
		{
			dfs(i);
			co++;
		}
	}
	printf("%d", co);
}

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

문제

문제

출처

ICPC

C/C++ 언어 BFS 로 했는데 시간 초과 나오네요 고수님들 부탁드립니다.

dudql92 3년 전 0

sr5757 3년 전 1

sonjaewon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말