(1) [C++, Java] 백준 No.1260 : DFS와 BFS

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터6-3-그래프-그래프의-탐색

 

# C++(인접 행렬 사용)

#include <iostream>
#include <queue>
#include <cstring>        // memset

using namespace std;

int v, e, startNum;
int arr[1001][1001];     // 인접행렬
bool check[1001];        // check배열
void dfs(int x);
void bfs(int x);

int main()
{
    /*정점의 개수, 간선의 개수, 탐색시작 정점의 번호 입력받기*/
    cin >> v >> e >> startNum;

    /*입력을 받아 인접행렬 만들기*/
    while(e--){
        int x, y;
        cin >> x >> y;
        arr[x][y] = arr[y][x] = 1; // 주어진 간선이 양방향이라고 하였으므로
    }

    /*인접행렬을 이용해서 DFS, BFS탐색하기*/
    dfs(startNum);
    cout << "\n";
    
    memset(check, false, sizeof(check));

    bfs(startNum);
    cout << "\n";
}

void dfs(int x){
    cout << x << " ";
    check[x] = true;

    for (int i = 1; i <= v; i++){
        if (check[i] == false && arr[x][i] == 1)
            dfs(i);
    }
}

void bfs(int x){
    queue<int> q;

    q.push(x);
    check[x] = true;

    while(!q.empty()){
        int currentNode = q.front();
        q.pop();
        cout << currentNode << " ";
        for(int i = 1; i <= v; i++){
            if(check[i] == false && arr[currentNode][i] == 1){
                q.push(i);
                check[i] = true;
            }
        }
    }
}

 

# C++(인접 리스트 사용)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int v, e, startNum;
vector<int> vec[1001];   // 인접리스트
bool check[1001];        // check배열
void dfs(int x);
void bfs(int x);

int main()
{
    /*정점의 개수, 간선의 개수, 탐색시작 정점의 번호 입력받기*/
    cin >> v >> e >> startNum;

    /*입력을 받아 인접리스트 만들기*/
    while(e--){
        int a, b;
        cin >> a >> b;
        // 주어진 간선이 양방향이라고 하였으므로
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    /*작은 번호의 노드부터 방문할 수 있도록 인접리스트를 정렬해줘야함*/
    for (int i = 1; i <= v; i++)
        sort(vec[i].begin(), vec[i].end());

    /*인접리스트를 이용해서 DFS, BFS탐색하기*/
    dfs(startNum);
    cout << "\n";
    
    memset(check, false, sizeof(check));
    
    bfs(startNum);
    cout << "\n";
}

void dfs(int x){
    cout << x << " ";
    check[x] = true;

    for (int i = 0; i < vec[x].size(); i++){
        int y = vec[x][i];
        if (check[y] == false)
            dfs(y);
    }
}

void bfs(int x){
    queue<int> q;

    q.push(x);
    check[x] = true;

    while(!q.empty()){
        int currentNode = q.front();
        q.pop();
        cout << currentNode << " ";
        for (int i = 0; i < vec[currentNode].size(); i++){
            int y = vec[currentNode][i];
            if(check[y] == false){
                q.push(y);
                check[y] = true;
            }
        }
    }
}

 

# C++(간선 리스트 사용)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <utility>
#include <algorithm>

using namespace std;

int v, e, startNum;

vector<pair<int, int>> edge;         // 간선리스트
int cnt[1001];                       // cnt 배열
bool check[1001];                    // check배열
void dfs(int x);
void bfs(int x);

int main()
{
    /*정점의 개수, 간선의 개수, 탐색시작 정점의 번호 입력받기*/
    cin >> v >> e >> startNum;

    /*입력을 받아 간선리스트 만들기*/
    while(e--){
        int a, b;
        cin >> a >> b;
        // 주어진 간선이 양방향이라고 하였으므로
        edge.push_back(make_pair(a, b));
        edge.push_back(make_pair(b, a));
    }

    /*간선리스트 정렬*/
    sort(edge.begin(), edge.begin() + edge.size());
    
    /*간선의 시작점을 기준으로 개수 카운트*/
    for (int i = 0; i < edge.size(); i++)
        cnt[edge[i].first] += 1;

    /*cnt 배열 누적값 구하기*/
    for (int i = 1; i <= v; i++)
        cnt[i] = cnt[i-1] + cnt[i];

    /*간선리스트를 이용해서 DFS, BFS탐색하기*/
    dfs(startNum);
    cout << "\n";
    
    memset(check, false, sizeof(check));
    
    bfs(startNum);
    cout << "\n";
}

void dfs(int x){
    cout << x << " ";
    check[x] = true;

    for (int i = cnt[x-1]; i <= cnt[x]-1; i++){   // edge[cnt[x-1]] ~ edge[cnt[x]-1]
        if (check[edge[i].second] == false)
            dfs(edge[i].second);
    }
}

void bfs(int x){
    queue<int> q;

    q.push(x);
    check[x] = true;

    while(!q.empty()){
        int currentNode = q.front();
        q.pop();
        cout << currentNode << " ";
        for (int i = cnt[currentNode-1]; i <= cnt[currentNode]-1; i++){     // edge[cnt[currentNode-1]] ~ edge[cnt[currentNode]-1]
            if(check[edge[i].second] == false){
                q.push(edge[i].second);
                check[edge[i].second] = true;
            }
        }
    }
}

 

# C++(dfs까지 비재귀 구현)

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>

using namespace std;

int v, e, startNum;
vector<int> vec[1001];   // 인접리스트
bool check[1001];        // check배열
void dfs(int x);
void bfs(int x);

int main()
{
    /*정점의 개수, 간선의 개수, 탐색시작 정점의 번호 입력받기*/
    cin >> v >> e >> startNum;

    /*입력을 받아 인접리스트 만들기*/
    while(e--){
        int a, b;
        cin >> a >> b;
        // 주어진 간선이 양방향이라고 하였으므로
        vec[a].push_back(b);
        vec[b].push_back(a);
    }

    /*작은 번호의 노드부터 방문할 수 있도록 인접리스트를 정렬해줘야함*/
    for (int i = 1; i <= v; i++)
        sort(vec[i].begin(), vec[i].end());

    /*인접리스트를 이용해서 DFS, BFS탐색하기*/
    dfs(startNum);
    cout << "\n";
    
    memset(check, false, sizeof(check));
    
    bfs(startNum);
    cout << "\n";
}

void dfs(int x){
    stack<int> st;

    st.push(x);
    check[x] = true;
    cout << x << " ";

    while(!st.empty()){
        int curruntNode = st.top();

        /*for 문에서 이동할 정점을 찾지 못했을 경우 pop해주기 위한 플래그*/
        bool is_finded = false;

        /*이동할 수 있는 정점을 1개 또는 0개 찾게되는 for문*/
        for(int i = 0; i < vec[curruntNode].size(); i++){
            int y = vec[curruntNode][i];
            if(check[y] == false)
            {
                check[y] = true;
                st.push(y);
                cout << y << " ";
                is_finded = true;
                break;
            }
        }

        /*현재의 위치에서 이동할 수 있는 정점을 찾지 못했다면 pop함*/
        if(!is_finded)
            st.pop();
    }
}

void bfs(int x){
    queue<int> q;

    q.push(x);
    check[x] = true;

    while(!q.empty()){
        int currentNode = q.front();
        q.pop();
        cout << currentNode << " ";
        for (int i = 0; i < vec[currentNode].size(); i++){
            int y = vec[currentNode][i];
            if(check[y] == false){
                q.push(y);
                check[y] = true;
            }
        }
    }
}

 

# Java(인접 리스트 사용)

import java.util.*;

public class Main {
    static ArrayList<Integer>[] a;
    static boolean[] c;
    public static void dfs(int x) {
        if (c[x]) {
            return;
        }
        c[x] = true;
        System.out.print(x + " ");
        for (int y : a[x]) {
            if (c[y] == false) {
                dfs(y);
            }
        }
    }
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        c[start] = true;
        while (!q.isEmpty()) {
            int x = q.remove();
            System.out.print(x + " ");
            for (int y : a[x]) {
                if (c[y] == false) {
                    c[y] = true;
                    q.add(y);
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int start = sc.nextInt();
        a = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = new ArrayList<Integer>();
        }
        for (int i=0; i<m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            a[u].add(v);
            a[v].add(u);
        }
        for (int i=1; i<=n; i++) {
            Collections.sort(a[i]);
        }
        c = new boolean[n+1];
        dfs(start);
        System.out.println();
        c = new boolean[n+1];
        bfs(start);
        System.out.println();
    }
}