백준 1260 bfs 와 dfs

1. map 으로 풀기 ! 

#include<iostream>	
#include<queue>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int N, M, V;
int map[1002][1002];
int arr[1002];
int x, y;
queue <int > q;
void dfs(int st) {

	for (int j = 1; j <= N; j++) {
		if (map[st][j] == 1 && arr[j] == 0) {
			printf("%d ", j); 
			arr[j] = 1;
			dfs(j);
		//	return;
		}
		
	}
	
}
void bfs() {

	while (!q.empty()) {
		int st = q.front();
		printf("%d ", st); 
		q.pop();
		for(int j = 1; j <= N; j++) {
			if (map[st][j] == 1 && arr[j] == 0) {
				arr[j] = 1;

				q.push(j);

			}

		}
	}

}
int main() {
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++) {
		scanf("%d%d", &x, &y);
		map[x][y] = 1;
		map[y][x] = 1;
	}

	arr[V] = 1;
	printf("%d ", V);
	dfs(V);

	printf("\n");
	memset(arr, 0, sizeof(arr));
	arr[V] = 1;
	printf("%d ", V); 

	for (int i = 1; i <= N; i++) {
		if (map[V][i] == 1) {
			arr[i] = 1;
			q.push(i);
		}
	}
	bfs();


	return 0;
}

 ** 핵심  

  printf("%d " V);

:: 띄어쓰기 할때 %d 앞뒤로 띄어쓰면 가능하다 

 

 

2. 시간을 더 줄여서 2차원 vector를 이용해서 풀기

#include<iostream>	
#include<queue>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int N, M, V;
vector <int> v[1002];
int arr[1002];
int x, y;
queue <int > q;

void dfs(int st) {
	for (int i = 0; i < v[st].size(); i++) {
		int k = v[st][i];
		if (arr[k] == 0) {
			arr[k] = 1;
			printf("%d ", k);
			dfs(k);
		}
	}
}
void bfs() {
	while (!q.empty()) {
		int st = q.front();
		q.pop();
		printf("%d ", st);
		for (int i = 0; i < v[st].size(); i++) {
			int k = v[st][i];
			if (arr[k] == 0) {
				arr[k] = 1;
				q.push(k);
			}
		}
	}

}
int main() {
	scanf("%d%d%d", &N, &M, &V);

	for (int i = 0; i < M; i++) {
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int i = 0; i < N; i++) {
		sort(v[i].begin(), v[i].end());
	}

	printf("%d ", V);
	arr[V] = 1;
	dfs(V)
;
	printf("\n");
	memset(arr, 0, sizeof(arr));
	
	q.push(V);
	arr[V] = 1;
	bfs();


	return 0;
}

 

 ** 핵심  

//선언
vector <int> v[1002]

//sort방법 
sort(v[i].begin(),v[i].end());

:: 2차원 배열 선언과 / sort 방법