1260 DFS 와 BFS

1260 DFS 와 BFS

1260 DFS 와 BFS

풀이코드

#include #include #include #include using namespace std; // 1260 DFS와 BFS int n, m, start; // 인접 리스트 vector adjList[1001]; bool isVisited[1001]; // bfs 를 위한 queue queue 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 << '

'; } 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 << '

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

해설

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

풀이

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

from http://private-k.tistory.com/133 by ccl(A) rewrite - 2021-10-02 18:27:05