백준/ 1260번(DFS와 BFS)/ C++ ; Vector와 sort함수 사용

 

문제 설명

 

DFS와 BFS를 구현하는 연습을 해볼 수 있는 기본 문제.

 

 

주의해야 할 점

1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문.

2. 입력으로 주어지는 간선은 양방향.

3. 간선이 없는 노드. 더 이상 방문할 수 있는 점이 없는 경우 종료되기 때문에, 어떠한 노드와도 연결되어 있지 않은 노드는 따로 처리해줄 필요가 없다.

 

 

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int c[1001];    //정점에 방문했는지 체크하는 배열
vector<int> a[1001];    //그래프 정보 저장하는 벡터

//처음 그래프를 구성할 때에 에지를 추가하는 함수
void insert_edge(int i, int j) {
	a[i].push_back(j);		//양방향 에지
	a[j].push_back(i);
}

void bfs(int start) {
	queue<int> q;
	q.push(start);
	c[start] = true;

	while (!q.empty()) {
		int w = q.front();
		q.pop();
		cout << w << ' ';
		for (int i = 0; i < a[w].size(); i++) {
			int y = a[w][i];
			if (!c[y]) {
				q.push(y);
				c[y] = true;
			}
		}
	}
}

void dfs(int n) {
	if (c[n]) return;

	cout << n << ' ';
	c[n] = true;
	for (int i = 0; i < a[n].size(); i++) {
		int y = a[n][i];
		if (!c[y])
			dfs(y);
	}
}

int main(void) {
	int N, M, V, x, y;
	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		insert_edge(x, y);    //에지 추가
	}

	for (int i = 1; i <= N; i++) {		//정점이 작은 것부터 방문하도록
		sort(a[i].begin(), a[i].end());
	}

	dfs(V);
	cout << endl;
	memset(c, 0, sizeof(c));    //정점에 방문했는지 체크하는 배열 초기화
	bfs(V);
	cout << endl;
}

 

디버깅 기록

: 처음에는 정점이 작은 것부터 방문하게 만들기 위해, 정점이 작은 것을 고르는 함수 select_edge를 만들어서 돌렸으나, 틀렸다는 결과가 나왔다. 반례를 직접 찾지는 못했지만 minvalue값을 1002로 초기화하는 부분이나 내가 이상함을 느끼지 못한 다른 부분에서 충분히 오류가 났을 것이라고 예상한다. 우선순위가 같을 때는 작은 것부터 혹은 큰 것부터 출력해야 한다면 출력하기 직전에 그 값을 고르기보다는, 전체를 한 번에 정렬하자.

 

 

 

코드 컨벤션

: 변수명에 의미를 부여하도록 더욱 노력하자. x,y도 from, to로 c도 visited로, a도 graph로 한다면 더욱 가독성 있는 코드가 될 것이다.