글 읽기 - [C++] 2606번 질문입니다

syoh0708 6년 전 0

풀이는 DFS로 구현했고

adj = 인접행렬, index = 현재 방문하는 점, count = 현재까지 연결된 점의 수, visited = 방문 여부를 나타내는 bool array

초기화 문제도 없어보이고(있나요..?), 양방향으로 넣어줬고, 몇 예시를 추가로(질문 참고하여) 넣어봤는데 어디서 잘못되었는지 잘 모르겠습니다.

혹시 array, vector를 전역으로 할당하지 않고 stack에 할당해서 그런가요?

array는 크기가 변하지 않으니 침범당할 염려는 없어보이고, vector는 문제가 생길수도 있다는 생각이 드네요.

어디서 문제가 발생할 수 있나요?

도움 부탁드립니다.

#include <iostream>
#include <vector>
using namespace std;

int dfs(vector <vector <int>> &adj, int index, int &count, bool *visited) {
	int i, v;
	count++;
	for (i = 0; i < adj[index].size(); i++) {
		v = adj[index][i];
		if (!visited[v]) {
			visited[v] = true;
			dfs(adj, v, count, visited);
		} 
	}
	return count;
}

int main() {
	int v, e, v1, v2, i, count = 0;

	cin >> v >> e;

	vector <vector <int>> adj(v+1);
	bool visited[v+1] = {};
	
	for (i = 0; i < v; i++) {
		cin >> v1 >> v2;
		adj[v1].push_back(v2);
		adj[v2].push_back(v1);
	}
	
	visited[1] = true;
	cout << dfs(adj, 1, count, visited) - 1;
	
	return 0;
}

djm03178 6년 전 0

애초에 예제도 제대로 안 됩니다. e개만큼 연결된 쌍을 입력받아야 되는데 v개만큼 입력받고 있습니다.

syoh0708 6년 전 0

감사합니다.

넣은 예제들 보니까 길지 않은 예제들만 넣어봤네요..

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

문제

문제

출처

ICPC

[C++] 2606번 질문입니다

syoh0708 6년 전 0

djm03178 6년 전 0

syoh0708 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말