[Python/Java] 백준 1260 - DFS와 BFS [DFS/BFS]

문제

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

 

해설

알고리즘 문제에서 자주 활용되는 DFS와 BFS 구현에 대한 문제였다. 모든 Vertex(정점)을 방문할 땐 DFS, BFS 모두 사용하여도 무관하지만 경로의 특징에 따라 처리가 되는 문제라면 DFS를 사용하는 것이 유리하다. 반면 최단거리를 구하는 문제는 BFS를 사용하는 것이 유리하다. 깊이 내려가지 않고 가까운 곳에서 탐색할 수 있기 때문이다. 참고로 간선은 Edge라고 표현한다.

 

Python

from sys import stdin


def dfs(graph: list, start: int, visited: list):
    dfs_result.append(str(start))
    visited[start] = True

    for neighbor in range(1, len(graph[start])):
        if not visited[neighbor] and graph[start][neighbor] == 1:
            dfs(graph, neighbor, visited)


def bfs(graph: list, start: int, visited: list):
    bfs_result.append(str(start))
    visited[start] = True

    queue = [start]
    while queue:
        start = queue.pop(0)
        for neighbor in range(1, len(graph[start])):
            if not visited[neighbor] and graph[start][neighbor] == 1:
                bfs_result.append(str(neighbor))
                visited[neighbor] = True
                queue.append(neighbor)


n, m, v = map(int, stdin.readline().split(" "))
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    v1, v2 = map(int, stdin.readline().split(" "))
    graph[v1][v2] = 1
    graph[v2][v1] = 1

visited = [False for _ in range(n+1)]
dfs_result = []
dfs(graph, v, visited)
print(" ".join(dfs_result))

visited = [False for _ in range(n+1)]
bfs_result = []
bfs(graph, v, visited)
print(" ".join(bfs_result))

 

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] condition = br.readLine().split(" ");
        int n = Integer.parseInt(condition[0]);
        int m = Integer.parseInt(condition[1]);
        int v = Integer.parseInt(condition[2]);

        int[][] graph = new int[n+1][n+1];
        int[] visited = new int[n+1];
        for(int i=0; i<m; i++){
            String[] edge = br.readLine().split(" ");
            int v1 = Integer.parseInt(edge[0]);
            int v2 = Integer.parseInt(edge[1]);
            graph[v1][v2] = 1;
            graph[v2][v1] = 1;
        }

        for(int i=0; i<n+1; i++){ visited[i] = 0; }
        dfs(graph, v, visited, sb);
        System.out.print(sb.append("\n").toString());

        sb.setLength(0);

        for(int i=0; i<n+1; i++){ visited[i] = 0; }
        bfs(graph, v, visited, sb);
        System.out.print(sb.append("\n").toString());
    }

    public static void dfs(int[][] graph, int start, int[] visited, StringBuilder sb) {
        sb.append(start).append(" ");
        visited[start] = 1;

        for(int neighbor=1; neighbor<graph[start].length; neighbor++){
            if(visited[neighbor]==0 && graph[start][neighbor]==1){
                dfs(graph, neighbor, visited, sb);
            }
        }
    }

    public static void bfs(int[][] graph, int start, int[] visited, StringBuilder sb) {
        sb.append(start).append(" ");
        visited[start] = 1;
        
        Queue<Integer> q = new LinkedList<>();
        q.add(start);

        while(!q.isEmpty()){
            start = q.poll();
            for(int neighbor=1; neighbor<graph[start].length; neighbor++){
                if(visited[neighbor]==0 && graph[start][neighbor]==1){
                    sb.append(neighbor).append(" ");
                    visited[neighbor] = 1;
                    q.add(neighbor);
                }
            }    
        }
    }
}