글 읽기 - 채점이 틀렸다고 나옵니다. 원인이 뭔지 알려주세요.

ahn4685 7년 전 0

인접행렬로 사이즈 먼저 구해서 일일히 체크하는 식으로 하였는데 정답은 똑같이 나옵니다만 왜 틀렸다고 나오는건가요?

#include<iostream>
#include<array>
#include<stack>
#include<queue>

using namespace std;

array<array<int, 1001>, 1001> arr;
array<bool, 1001> visited;
array<int, 1001> size1;

void DFS(int fir)
{
	stack<int> St;
	bool chk;
	int visit = fir,i,next;
	St.push(visit);
	visited[visit] = true;

	cout << visit << " ";

	while (!St.empty())
	{
		chk = false;

		for (i = 1; i <= size1[visit]; i++)
		{
			next = arr[visit][i];
			if (visit == i)
				continue;
			if (next == 1 && visited[i] == false)
			{
				visited[i] = true;
				visit = i;
				cout << visit << " ";
				St.push(visit);
				chk = true;
				break;
			}
		}
		
		if (chk == false)
		{
			St.pop();
			if (!St.empty())
				visit = St.top();
		}
	}
}

void BFS(int fir)
{
	queue<int> Q;
	bool chk;
	int visit = fir, i,next,cnt=1;
	Q.push(visit);
	cout << visit << " ";
	visited[visit] = true;

	while (!Q.empty())
	{
		chk = false;

		for (i = 1; i <= size1[visit]; i++)
		{
			if (visit == i)
				continue;
			
			next = arr[visit][i];
			
			if (next == 1 && visited[i] == false)
			{
				visited[i] = true;
				cout << i << " ";
				Q.push(i);
				chk = true;
			}
		}

		visit = ++cnt;

		if (chk == false)
		{
			Q.pop();
			if (!Q.empty())
				visit = Q.front();
		}
	}

}
void adj_mat_init(void)
{
	int i, j;
	for (i = 1; i < 1001; i++)
	{
		for (j = 1; j < 1001; j++)
		{
			if (arr[i][j] == 1)
				size1[i] = j;
		}
	}
}

int main(void)
{
	int n, m, v,i,j;

	cin >> n >> m >> v;
	
	while (m--)
	{
		cin >> i >> j;
		arr[i][j] = arr[j][i] = 1;
	}
	adj_mat_init();

	visited.fill(false);
	DFS(v);
	cout << endl;

	visited.fill(false);
	BFS(v);

	return 0;
}

ahn4685 7년 전 0

ADJ_MAT_INIT부분을 지우고 제한범위 설정을 n개로 변경하였습니다.

해결되었는데, 컴파일 잘되고 실행 잘되지만 실행속도가 8MS인데 더 늘리는 방법이 뭐가 있을까요?

ehddml3 7년 전 0

vector를 사용하면 인접리스트 형식으로 더 편하게 구현 가능합니다. 인접행렬은 밀집도가 작으면 시간이 많이 걸려서 그런거 같네요

vector<vector<int> > adj;
vector<bool> visited;

void DFS(int here){

    visited[here]=true;
    for(int i=0;i<adj[here].size();i++){
        int next = adj[here][i];
        if(!visited[next])
            DFS(next);
    }
}

int main(){
    
    ...
    
    adj.resize(n+1);

    int a,b;
    for(int i=0;i<m;i++){
        scanf("%d %d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }                                // 그래프 입력 받기.
    
    ...
}

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

문제

문제

출처

ICPC

채점이 틀렸다고 나옵니다. 원인이 뭔지 알려주세요.

ahn4685 7년 전 0

ahn4685 7년 전 0

ehddml3 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말