난이도

Silver 2

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력

3 1 2 5 4
3 1 4 2 5

문제 검토

대놓고 BFS, DFS를 사용하는 쉬운 문제이다.
인접 리스트 형식으로 그래프가 주어진다.

풀이(python)

Python

n,m,v = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(m)]
graph = [[] for _ in range(n+1)]
visited=[False for _ in range(n+1)]
for x in range(m):
    graph[edge[x][0]].append(edge[x][1])
    graph[edge[x][1]].append(edge[x][0])
for x in range(len(graph)):
    graph[x]=sorted(graph[x])
from collections import deque
def bfs():
    q=deque()
    q.append(v)
    visited[v]=False
    print(v,end=' ')
    while q:
        curv=q.popleft()
        for x in graph[curv]:
            if not visited[x]:
                continue
            q.append(x)
            visited[x]=False
            print(x,end=' ')
def dfs(idx):
    if visited[idx]:
        return
    visited[idx]=True
    print(idx,end=' ')
    for x in graph[idx]:                
        dfs(x)
dfs(v)            
print()
bfs()

Java

import java.util.*;
import java.io.*;
public class Main {
    static int n, m, v;
    //graph배열을 선언 다만 객체로는 Integer타입의 요소를 받는 ArrayList가 들어올 수 있음
    static ArrayList<Integer> graph[];
    //visited 변수를 선언 다만 객체로는 boolean타입의 요소를 받는 ArrayList가 들어올 수 있음
    static ArrayList<Boolean> visited;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = sc.nextInt();
        //graph 배열에 ArrayList의 공간을 n+1만큼 할당하겠다.
        graph = new ArrayList[n + 1];
        //visited변수에 ArrayList의 공간을 할당하겠다.
        visited = new ArrayList<>();
        for(int i=0; i<n+1;i++){
            //visited에 false를 append
            visited.add(false);
        }
        for(int i=0; i<n+1; i++){
            //ArrayList의 공간을 n+1개만큼 할당했으니 각각 할당된 공간에 ArrayList의 공간을 할당한다.(2차원ArrayList)
            graph[i]=new ArrayList<>();
        }
        //간선을 입력 받아 인덱스 기준 정점의 그래프 완성
        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }
        //sort
        for(int i=0; i<graph.length;i++){
            Collections.sort(graph[i]);
        }
        dfs(v);
        System.out.println();
        bfs();
    }
    public static void dfs(int idx){
        if (visited.get(idx)){
            return;
        }
        visited.set(idx,true);
        System.out.printf("%d ",idx);
        for(int i = 0; i<graph[idx].size(); i++){
            dfs(graph[idx].get(i));
        }
    }
    public static void bfs(){
        //Integer 타입의 요소를 받는 Queue 객체를 받을 수 있는 변수 q에 LinkedList 객체를 할당한다.
        Queue<Integer> q=new LinkedList<>();
        //큐에 시작정점을 append
        q.add(v);
        //방문처리
        visited.set(v,false);
        System.out.printf("%d ",v);
        while(!q.isEmpty()){
            //q에서 pop한다
            int idx=q.poll();
            for(int i=0;i<graph[idx].size();i++){
                if(!visited.get(graph[idx].get(i))){
                  continue;
                }
                System.out.printf("%d ",graph[idx].get(i));
                q.add(graph[idx].get(i));
                visited.set(graph[idx].get(i),false);
            }
        }
    }
}

아이디어

#정점의 개수를 기준으로 각각 간선을 통해 이어져 있는 그래프의 형태를 만든다.
#정점은 인덱스로 한다.

시간복잡도

#정점은 1,000개 간선은 1,0000개 까지의 범위가 있으므로 O(v*e)로 10,000,000의 연산횟루를 갖게 된다. okay

걸린 시간

17:33

총평

어렵지 않은 기본문제이다.