[Python][C++] 1260번 DFS와 BFS

문제

https://www.acmicpc.net/problem/1260

 

 

코드

1. Python

n, m, v = map(int, input().split())

graph = [[0] * (n + 1) for _ in range(n + 1)]

# 방문 상태를 체크할 리스트 (DFS와 BFS 각각에 대해 별도로 관리)
visited = [0] * (n + 1)
visited2 = [0] * (n + 1)

# m개의 간선 정보를 받아서 그래프를 구성
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1  # a에서 b로 가는 간선
    graph[b][a] = 1  # b에서 a로 가는 간선 (양방향)

# 깊이 우선 탐색 함수
def dfs(V):
    # 현재 노드를 방문 처리
    visited[V] = 1
    print(V, end=' ')
    # 모든 노드를 순회하며
    for i in range(n + 1):
        # 연결되어 있고 아직 방문하지 않은 노드가 있다면
        if graph[V][i] == 1 and visited[i] == 0:
            # 해당 노드로 DFS 재귀 호출
            dfs(i)

# 너비 우선 탐색 함수
def bfs(V):
    q = [V]  # 큐 초기화
    visited2[V] = 1  # 시작 노드 방문 처리
    while q:
        V = q.pop(0)  # 큐에서 노드 추출
        print(V, end=' ')
        # 모든 노드를 순회하며
        for i in range(n + 1):
            # 연결되어 있고 아직 방문하지 않은 노드가 있다면
            if graph[V][i] == 1 and visited2[i] == 0:
                q.append(i)  # 큐에 추가
                visited2[i] = 1  # 방문 처리

# 시작 노드 v에서 DFS 실행
dfs(v)
print()
# 시작 노드 v에서 BFS 실행
bfs(v)

 

2. C++

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

// DFS 함수 정의
void dfs(int v, int n, const vector<vector<int>>& graph) {
    stack<int> s; // 스택 선언
    vector<int> visited(n + 1); // 방문 여부를 저장할 벡터

    s.push(v); // 시작 노드를 스택에 푸시

    // 스택이 비어있지 않는 동안 반복
    while (!s.empty()) {
        v = s.top(); // 현재 노드
        s.pop(); // 스택에서 노드를 꺼냄

        // 현재 노드를 방문하지 않았다면
        if (!visited[v]) {
            visited[v] = 1; // 방문 처리
            cout << v << " "; // 노드 출력
        }

        // 현재 노드의 인접 노드를 역순으로 검사
        for (int i = graph[v].size() - 1; i >= 0; --i) {
            int nv = graph[v][i]; // 인접 노드

            // 인접 노드를 방문하지 않았다면 스택에 푸시
            if (!visited[nv]) {
                s.push(nv);
            }
        }
    }
}

// BFS 함수 정의
void bfs(int v, int n, const vector<vector<int>>& graph) {
    queue<int> q; // 큐 선언
    vector<int> visited(n + 1); // 방문 여부를 저장할 벡터

    q.push(v); // 시작 노드를 큐에 푸시
    visited[v] = 1; // 시작 노드 방문 처리

    // 큐가 비어있지 않는 동안 반복
    while (!q.empty()) {
        v = q.front(); // 큐에서 노드를 꺼냄
        cout << v << " "; // 노드 출력
        q.pop(); // 노드 제거

        // 현재 노드의 모든 인접 노드를 검사
        for (int nv : graph[v]) {
            // 인접 노드를 방문하지 않았다면
            if (!visited[nv]) {
                q.push(nv); // 큐에 푸시
                visited[nv] = 1; // 방문 처리
            }
        }
    }
}

int main() {
    int n, m, v;

    cin >> n >> m >> v;

    vector<vector<int>> graph(n + 1);
    int v1, v2;

    // 간선 정보 입력 받기
    while (m--) {
        cin >> v1 >> v2;
        graph[v1].emplace_back(v2); // 양방향 간선 추가
        graph[v2].emplace_back(v1);
    }

    // 그래프의 각 리스트를 정렬하여 노드 번호가 작은 순서대로 탐색
    for (int i = 0; i <= n; i++)
        sort(graph[i].begin(), graph[i].end());

    dfs(v, n, graph); // DFS 실행
    cout << "\n";
    bfs(v, n, graph); // BFS 실행

    return 0;
}

 

 

풀이 

DFS와 BFS로 구현하는 간단한 문제.

 

 

DFS 참고

https://ehdbs0903.tistory.com/entry/깊이-우선-탐색-DFSDepth-First-Search-알고리즘

[Algorithm] 깊이 우선 탐색 / DFS(Depth-First Search) 알고리즘

 

BFS 참고

https://ehdbs0903.tistory.com/entry/Algorithm-너비-우선-탐색-BFSBreadth-First-Search-알고리즘

[Algorithm] 너비 우선 탐색 / BFS(Breadth-First Search) 알고리즘