백준 1260 - DFS와 BFS

링크

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

문제 풀이

그래프탐색에 있어 가장 기본적인 DFS, BFS를 사용해볼 수 있는 유형이다. 좌표 자체가 존재하지 않아 1차원적인 check방식을 통해 탐색해 나간다.

cpp 코드

#include <bits/stdc++.h>
using namespace std;

// 점점의 개수 : N, 간산의 개수 M, 탐색을 시작할 정점의 번호 V
int N, M, V;
bool check_dfs[1010];
bool check_bfs[1010];
int graph[1010][1010];

void bfs(int start) {
    queue<int> q;
    q.push(start);
    check_bfs[start] = true;

    while (!q.empty()) {
        int cnt = q.front();
        q.pop();

        cout << cnt << ' ';

        for (int i = 1; i <= N; i++) {
            if (graph[cnt][i] == 1 && check_bfs[i] == false) {
                check_bfs[i] = true;
                q.push(i);
            }
        }
    }
}

void dfs(int depth, int cnt) {
    check_dfs[cnt] = true;

    if (N <= depth) {
        return;
    }

    cout << cnt << ' ';

    for (int i = 1; i <= N; i++) {
        if (graph[cnt][i] == 1 && check_dfs[i] == false) {
            dfs(depth + 1, i);
        }
    }
}

int main(void) {
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;

        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    dfs(0, V);
    cout << '\n';
    bfs(V);

    return 0;
}

java 코드

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int n, m, v;
    static int map[][];
    static boolean bfs_check[];
    static boolean dfs_check[];

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = sc.nextInt();

        map = new int[n + 1][n + 1];

        for (int i = 0; i < m; i++) {
            int from, to;
            from = sc.nextInt();
            to = sc.nextInt();

            map[from][to] = 1;
            map[to][from] = 1;
        }
        bfs_check = new boolean[n + 1];
        dfs_check = new boolean[n + 1];

        dfs(v);
        System.out.println();
        bfs(v);

        sc.close();
    }

    static void dfs(int node) {
        System.out.print(Integer.toString(node) + ' ');
        dfs_check[node] = true;

        for (int i = 1; i <= n; i++) {
            if (map[node][i] == 1 && dfs_check[i] == false) {
                dfs(i);
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(start);
        bfs_check[start] = true;

        System.out.print(Integer.toString(start) + ' ');

        while (!q.isEmpty()) {
            int cnt = q.remove();

            for (int i = 1; i <= n; i++) {
                if (map[cnt][i] == 1 && bfs_check[i] == false) {
                    bfs_check[i] = true;
                    q.offer(i);
                    System.out.print(Integer.toString(i) + ' ');
                }
            }
        }
    }
}

python 코드

def bfs(start):
    queue = [start]
    bfs_check = [start]

    while queue:
        cnt_node = queue.pop(0)

        for next_node in range(len(matrix[cnt_node])):
            if(matrix[cnt_node][next_node] == 1 and next_node not in bfs_check):
                bfs_check.append(next_node)
                queue.append(next_node)

    return bfs_check


def dfs(cnt_node):
    dfs_check.append(cnt_node)

    for next_node in range(len(matrix[cnt_node])):
        if(matrix[cnt_node][next_node] == 1 and next_node not in dfs_check):
            dfs(next_node)


N, M, V = map(int, input().split())
matrix = [[0] * (N+1) for i in range(N+1)]
dfs_check = []

for i in range(M):
    point = list(map(int, input().split()))
    matrix[point[0]][point[1]] = 1
    matrix[point[1]][point[0]] = 1

dfs(V)
print(*dfs_check)
print(*bfs(V))