1260 DFS 와 BFS

1260 DFS 와 BFS

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 1260 DFS와 BFS

int n, m, start;

// 인접 리스트
vector<int> adjList[1001];

bool isVisited[1001];

// bfs 를 위한 queue
queue<int> q;

void dfs(int node){
	// 도착하자마자 방문했다고 check
	isVisited[node] = true;
	cout << node << ' ';
	
	for(int i = 0; i < adjList[node].size(); i++){
		// 다음 node
		int nextNode = adjList[node][i];
		
		// 방문했었다면 continue
		if(isVisited[nextNode]) continue;
		dfs(nextNode);
	}
}

void bfs(int start){
	// 출발점을 q 에 넣는다.
	q.push(start);
	isVisited[start] = true;
	cout << q.front() << ' ';
	
	// q가 비면 탐색 종료
	while(!q.empty()){
		// 현재 노드를 q 의 맨 앞으로 지정한다.
		int currentNode = q.front();
		// 현재 노드를 큐에서 제거한다.
		q.pop();
		
		// 현재 노드와 연결되어 있는 모든 노드를 살펴보자.
		for(int i = 0; i < adjList[currentNode].size(); i++){
			int nextNode = adjList[currentNode][i];
			
			// 방문했다면 생략
			if(isVisited[nextNode]) continue;
			
			// 현재 노드와 연결되어 있는 모든 nextNode 를 q에 넣는다.
			else{
				q.push(nextNode);
				isVisited[nextNode] = true;
				cout << nextNode << ' ';
			}
		}
	}
	cout << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n >> m >> start;
	
	for(int i = 0; i < m; i++){
		int from, to;
		cin >> from >> to;
		adjList[from].push_back(to);
		adjList[to].push_back(from);
	}
	
	// input 이 어떤 순서로 들어올지 알 수 없기에 오름차순으로 인접 리스트를 정렬해준다.
	for(int i = 1; i <= n; i++){
		sort(adjList[i].begin(), adjList[i].end());
	}

	
	fill_n(isVisited, 1001, false);
	dfs(start);
	cout << '\n';

	fill_n(isVisited, 1001, false);
	
	bfs(start);
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점