작성 코드

import java.io.*;
import java.util.*;

public class DFSBFS_1260 {
    private static ArrayList<ArrayList<Integer>> graph;
    private static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // n: 정점 갯수,  m: 간선 갯수, v: 시작 정점
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        for(int i = 1; i <= n; i++){
            Collections.sort(graph.get(i));
        }

        visited = new boolean[n + 1];

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

        visited = new boolean[n + 1];

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

    }

    public static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int next : graph.get(v)) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next);
            }
        }
    }

    public static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");

            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }
    }
}

설명

자료구조 및 로직

이 코드는 DFS (깊이 우선 탐색)과 BFS (너비 우선 탐색) 알고리즘을 사용하여 그래프를 탐색하는 프로그램입니다.

• 입력 받기

  • 첫 번째 줄에서 정점의 개수 n, 간선의 개수 m, 시작 정점 v를 입력 받습니다.
  • 입력은 BufferedReader를 사용하여 받습니다.

• 그래프 구성하기

  • graph라는 2차원 ArrayList를 생성합니다. 이는 각 정점마다 연결된 정점들의 리스트를 저장하기 위한 용도입니다.
  • n개의 정점에 대해 빈 리스트를 생성하여 graph에 추가합니다.
  • 다음 m개의 줄에서 간선 정보를 입력 받고, 해당 간선의 시작 정점과 끝 정점을 graph에 추가합니다. 이때 양방향 간선이므로 양쪽 정점에 모두 추가합니다.

• 그래프 정렬하기

  • 각 정점의 연결된 정점 리스트를 오름차순으로 정렬합니다. 이는 출력 결과를 사전 순으로 보여주기 위함입니다.

• DFS 탐색
  • visited라는 boolean 배열을 생성하여 방문한 정점을 표시합니다.
  • dfs 함수를 호출하여 시작 정점 v부터 DFS 탐색을 시작합니다.
  • 현재 정점 v를 방문했음을 표시하고, 정점 번호를 출력합니다.
  • 현재 정점에 연결된 정점들을 순회하면서 방문하지 않은 정점이 있다면, 해당 정점을 방문하고 dfs 함수를 재귀적으로 호출합니다.

• BFS 탐색
  • Queue인터페이스를 구현한 LinkedList를 사용하여 BFS 탐색을 위한 큐를 생성합니다.
  • 시작 정점 v를 큐에 추가하고 방문했음을 표시합니다.
  • 큐가 비어있지 않은 동안 아래 과정을 반복합니다.
    • 큐에서 정점을 하나 꺼내고, 해당 정점 번호를 출력합니다.
    • 해당 정점에 연결된 정점들 중 방문하지 않은 정점이 있다면, 큐에 추가하고 방문했음을 표시합니다.

• 출력
  • DFS 탐색 결과와 BFS 탐색 결과를 각각 출력합니다.

자바스크립트

const readline = require('readline');

function dfs(v, visited, graph) {
  visited[v] = true;
  process.stdout.write(v + ' ');

  for (const next of graph[v]) {
    if (!visited[next]) {
      dfs(next, visited, graph);
    }
  }
}

function bfs(v, visited, graph) {
  const queue = [];
  queue.push(v);
  visited[v] = true;

  while (queue.length > 0) {
    const current = queue.shift();
    process.stdout.write(current + ' ');

    for (const next of graph[current]) {
      if (!visited[next]) {
        queue.push(next);
        visited[next] = true;
      }
    }
  }
}

function main() {
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
  });

  let n, m, v;
  let graph = [];

  rl.on('line', (line) => {
    const tokens = line.trim().split(' ');

    if (n === undefined) {
      n = parseInt(tokens[0]);
      m = parseInt(tokens[1]);
      v = parseInt(tokens[2]);

      for (let i = 0; i <= n; i++) {
        graph.push([]);
      }
    } else {
      const start = parseInt(tokens[0]);
      const end = parseInt(tokens[1]);

      graph[start].push(end);
      graph[end].push(start);
    }
  }).on('close', () => {
    for (let i = 1; i <= n; i++) {
      graph[i].sort((a, b) => a - b);
    }

    const visited = new Array(n + 1).fill(false);

    dfs(v, visited, graph);
    process.stdout.write('\n');

    visited.fill(false);

    bfs(v, visited, graph);
    process.stdout.write('\n');
  });
}

main();

파이썬

from collections import deque

def dfs(v, visited, graph):
    visited[v] = True
    print(v, end=' ')

    for next in graph[v]:
        if not visited[next]:
            dfs(next, visited, graph)

def bfs(v, visited, graph):
    queue = deque()
    queue.append(v)
    visited[v] = True

    while queue:
        current = queue.popleft()
        print(current, end=' ')

        for next in graph[current]:
            if not visited[next]:
                queue.append(next)
                visited[next] = True

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

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

    for _ in range(m):
        start, end = map(int, input().split())

        graph[start].append(end)
        graph[end].append(start)

    for i in range(1, n + 1):
        graph[i].sort()

    visited = [False] * (n + 1)

    dfs(v, visited, graph)
    print()

    visited = [False] * (n + 1)

    bfs(v, visited, graph)
    print()

if __name__ == '__main__':
    main()