백준(BOJ) 1260 : DFS와 BFS (그래프 탐색 쌩기초)

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

 

기본적으로 dfs, bfs를 구현할 수 있는 지 문제이다. 상징성 있는 문제로 구실을 갖추기 위해 넣어 놓는다.

 

from sys import stdin
from collections import defaultdict
from collections import deque
def dfs(graph, visited, start):
    if(start not in visited):
        visited.add(start)
        print(start, end=' ')

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

def bfs(graph, start):
    que=deque([start])
    visited=set([start])
    while(que):
        v=que.popleft()
        print(v, end=' ')

        for u in range(len(graph)):
            if(graph[v][u]==1 and u not in visited):
                que.append(u)
                visited.add(u)
        
def main():
    vertex, edge, start=map(int, stdin.readline().split())
    
    graph=[[0]*(vertex+1) for _ in range(vertex+1)]
    for _ in range(edge):
        f,t=map(int, stdin.readline().split())
        graph[f][t]=1
        graph[t][f]=1

    visited=set()
    dfs(graph, visited, start)
    print()
    bfs(graph, start)

main()

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static void dfs(List<Integer>[] graph, boolean[] visited, int start) {
        for (int i = 0; i < graph[start].size(); i++) {
            int next = graph[start].get(i);
            if (!visited[next]) {
                visited[next] = true;
                System.out.printf("%d ", next);
                dfs(graph, visited, next);
            }
        }
    }

    static void bfs(List<Integer>[] graph, int start) {
        boolean[] visited = new boolean[graph.length + 1];
        visited[start] = true;
        System.out.printf("%d ", start);
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        while (!que.isEmpty()) {
            start = que.poll();
            for (int i = 0; i < graph[start].size(); i++) {
                int next = graph[start].get(i);
                if (!visited[next]) {
                    System.out.printf("%d ", next);
                    que.add(graph[start].get(i));
                    visited[next]=true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        //무방향 희소이므로 인접리스트이용.
//        List<List<Integer>> graph=new LinkedList<>();//이 방법으로는 감이 안옴.
        List<Integer>[] graph = new LinkedList[n + 1];
        for (int i = 1; i < n + 1; i++)
            graph[i] = new LinkedList<>();
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph[from].add(to);
            graph[to].add(from);
        }
        for (int i = 1; i < n + 1; i++)
            Collections.sort(graph[i]);

        boolean[] visited = new boolean[n + 1];
        System.out.printf("%d ", start);
        visited[start] = true;
        dfs(graph, visited, start);
        System.out.println();
        bfs(graph, start);

    }
}