글 읽기 - DFS로 구현했는데 왜 틀린걸까요?

(追記) (追記ここまで)

DFS로 구현했는데 왜 틀린걸까요?

5567번 - 결혼식

lsm990429 2년 전 0

DFS로 구현했는데 왜 틀린걸까요? 아무리 생각해도 모르겠네요..

반례가 있다면 반례만 주셔도 감사합니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, cnt = -1;
vector<vector<int>> vt;
vector<bool> visit;
void dfs(int v, int depth) {
	if (visit[v] || depth > 2) return; // 이미 방문했거나 시작점(1)에서 깊이 2초과인경우
	visit[v] = true;
	cnt++;
	if (!vt[v].empty() && vt[v][0] == 1) depth = 1; // 만약 시작점(1)과 바로 연결되어 있는경우 -> 깊이를 1로 변경
	for (auto a : vt[v]) dfs(a, depth+1); // 다음 정점을 방문할 때 깊이를 1증가시킴
}
int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vt.resize(n+1);
	visit.resize(n+1);
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		vt[a].push_back(b);
		vt[b].push_back(a);
	}
	for (auto v : vt) { // vt[i][0] == 1이 되도록(vt[i]사이즈가 0이 아닌경우)
		sort(v.begin(), v.end());
	}
	dfs(1, 0);
	cout << cnt;
	return 0;
}

gravekper 2년 전 0

31번째 줄의 for loop가 잘못되었습니다.

위 코드에서 v의 타입은 vector<int>입니다. 반복문이 진행되면서 v에는 실제로 정렬하려던 배열의 복사본이 들어옵니다.

의도한 대로 작동하게 하려면 아래와 같이 레퍼런스를 써야 합니다.

	for (auto &v : vt) {

lsm990429 2년 전 0

아 그렇네요. 미처 생각 못했어요. 감사합니다.

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

DFS로 구현했는데 왜 틀린걸까요?

lsm990429 2년 전 0

gravekper 2년 전 0

lsm990429 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말