[BOJ] 백준 1260번 : DFS와 BFS C++ : 아주정은

회사와서 한문제 푸는데 이문제는 제법 고민을 많이했던것같다.

가장 기본에 충실한 문제 같으면서도, 막상 어떻게 노드들의 구현을 해야할지 의문이 많이 들었다.

배열로 board를 만들어야할까 vector로 만들어야할까 고민도 굉장히 많이했다.

DFS를 구현할때는 stack을 쓸까 재귀를 쓸까도 고민을 많이했는데, 스택보다 재귀가 편하다고 판단되어 재귀를 사용하였다. 어짜피 DFS는 한곳 쭉~~~파다가 막히면 돌아오는 개념이기 때문에 재귀가 그 개념과 부합되는 이미지라고 판단했기 때문이다.

BFS는 평소 하던대로 queue를 사용하였다. 방문 여부를 묻고 큐에 넣고 출력을 해주었다.

내 소스코드에서 큐는 하나 선언했다. 코드 제출도 1번만 하였다. 이건 말그대로 당구장 아니지만 원큐였다.

참고하고 댓글로 피드백 주면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int board[1002][1002];
bool vis[1002];

void dfs(int v) {

	cout << v << " ";
	vis[v] = true;
	int i = 0;
	while (board[v][i]) {
		if (vis[board[v][i]] == false) {
			dfs(board[v][i]);
		}
		i++;
	}
}

void bfs(int v) {
	queue<int> Q;
	Q.push(v);
	vis[v] = true;
	
	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();
		cout << cur << " ";
		int i = 0;
		while (board[cur][i]) {
			int node_num = board[cur][i];
			if (vis[node_num] == false) {
				Q.push(node_num);
				vis[node_num] = true;
			}
			i++;
		}
	}
}

void board_initialize() {
	for (int i = 0; i < 1002; i++) {
		for (int j = 0; j < 1002; j++) {
			board[i][j] = 0;
		}
	}
}

void vis_initialize() {
	for (int i = 0; i < 1002; i++) {
		vis[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M, V;
	int a, b;
	cin >> N >> M >> V;
	
	//배열 초기화
	board_initialize();
	vis_initialize();
	
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		int j = 0, k = 0;
		while (board[a][j]) {
			j++;
		} // 간선 넣을 곳 찾기
		board[a][j] = b;

		while (board[b][k]) {
			k++;
		}
		board[b][k] = a;
	} // 양방향 노드 간선 추가하기


	for (int i = 1; i <= N; i++) {
		int j = 0;
		while (board[i][j]) {
			j++;
		}
		sort(board[i], board[i]+j);
	} // board 오름차순으로 정렬

	dfs(V);
	cout << endl;
	vis_initialize(); // 방문 여부 초기화
	bfs(V);
}