1260번

1260번 - DFS 와 BFS

DFS와 BFS.. 1년 전에 풀이기록을 보니까 10번 정도 제출해서 못 맞추고 넘어갔지만

그래도 나름 PS 를 조금 풀어보고 난 후에는 풀 수 있었다.

그떄는 DFS 가 너무 어려웠었다. 재귀 개념 자체가.. 근데 지금 완전 탐색, DP를 재귀로 풀면서 그나마 약간 감을 잡은 것 같다.

이런식으로 간선이 연결된 그래프를 풀 때 나는 주로 vector를 사용한다.

그리고 for문으로 항상 그 벡터의 사이즈 만큼 돌려주는 것을 익숙하게 사용하고 손에 익어서 계속 사용하는 것 같다.

노드와 정점을 표현하는 방법은 2가지 정도 있는거 같은데 나는 이게 익숙하다.

인접행렬 표현보다는 vector를 이용한 인접리스트로..

오랜만에 BFS DFS 라 처음에는 정점 방문 체크를 제대로 안해서 무한루프가 돌았지만 ... 그래도 이정도는 풀 수 있는 것 같다

정점 방문 할때 작은 순서부터 방문하다 보니 sort 함수를 써서 오름차순 정렬을 하고 문제를 풀었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
int N, M, S;
vector<int> node[1001];
queue<int> q;
bool check[1001];
void dfs(int start)
{
    
    cout << start << " ";
    
    check[start] = true;
    for (int i = 0; i < node[start].size(); i++)
    {
        if (!check[node[start][i]])
        {
        
            dfs(node[start][i]);
        }
    }
 
    return;
}
 
void bfs(int start)
{
 
    check[start] = true;
    q.push(start);
 
    while (!q.empty())
    {
        int x = q.front();
        cout << x << " ";
        q.pop();
 
        for (int i = 0; i < node[x].size(); i++)
        {
            if (!check[node[x][i]])
            {
                q.push(node[x][i]);
                check[node[x][i]] = true;
            }
        }
    }
 
}
int main()
{
 
    cin >> N >> M >> S;
 
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        node[b].push_back(a);
        node[a].push_back(b);
    }
 
    for (int i = 1; i <= N; i++)
    {
        sort(node[i].begin(), node[i].end());
    }
 
    dfs(S);
    cout << endl;
    memset(check, false, sizeof(check));
    bfs(S);
 
    return 0;
}