스노우보드 참 좋아하는데 맨날 키보드 앞에만 있네

백준 1260 : DFS와 BFS 본문

개발/Algorithm

백준 1260 : DFS와 BFS

워너-비 2018. 3. 6. 18:30
시간 제한메모리 제한제출정답맞은 사람정답 비율
5 초128 MB313669823592929.433%

문제

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

입력

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

출력

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

예제 입력 

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

예제 출력 

1 2 4 3
1 2 3 4



문제 분석


그래프의 정보를 입력받은 후 DFS와 BFS 탐색을 수행하여 두 알고리즘 결과를 출력하는 간단한 문제이다.

DFS, BFS에 대한 이해가 부족하다면 하단 링크를 참고하기 바란다.

그래프의 탐색 알고리즘 : DFS, BFS


먼저 입력을 통해 그래프의 정보를 입력받아야한다.

정점의 개수, 간선의 개수, 시작 정점을 입력받은 후 간선이 연결하는 두 정점의 번호를 인접행렬을 이용하여 저장한다.


이후 BFS와 DFS를 구현한다.


너비우선탐색인 BFS는 자료구조인 큐를 이용하여 구현한다.

깊이우선탐색인 DFS는 인접행렬에 저장된 순서대로 탐색을 수행하며, 함수의 재귀를 이용한다.

방문한 노드에 대한 정보를 boolean 타입의 check[] 변수배열에 저장한다. (visited == 1, not visited == 0)

BFS를 수행한 후 DFS 수행 전에 check[] 변수배열을 초기화 해주는 것을 잊지 말아야 한다.



소스코드


backjoon1260.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package backjoon;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class backjoon1260 {
    
    // 그래프의 정보를 저장할 인접행렬
    static int node[][] = new int[1001][1001];
    // 방문한 노드를 표시할 배열
    static boolean check[] = new boolean[1001];
    
    
    public static void main(String[] args) {
        
        Scanner s = new Scanner(System.in);
        // 정점의 개수 입력
        int n = s.nextInt();
        // 간선의 개수 입력
        int m = s.nextInt();
        // 탐색을 시작할 정점 번호 입력
        int v = s.nextInt();
        
        // 간선이 연결하는 두 정점의 번호를 인접행렬을 통해 저장
        for(int i = 0 ; i < m ; i++) {
            int x = s.nextInt();
            int y = s.nextInt();
            
            node[x][y] = 1;
            node[y][x] = 1;
        }
        
        // dfs 실행
        dfs(v);
        
        // check 배열 초기화 및 줄바꿈
        for(int i = 1 ; i < 1001 ; i++)
            check[i] = false;
        System.out.println( );
        
        // bfs 실행
        bfs(v);
    }
    
    public static void bfs(int v) {
        Queue<Integer> q = new LinkedList();
        q.add(v);
        check[v] = true;
        
        while(!q.isEmpty()) {
            int tmp = q.poll();
            System.out.print(tmp + " ");
            for(int i = 1 ; i < 1001; i++) {
                if(node[tmp][i] == 1 && !check[i]) {
                    check[i] = true;
                    q.add(i);
                }
            }
        }
    }
    
    public static void dfs(int v) {
        System.out.print(v);
        check[v] = true;
        for(int i = 1 ; i < 1001; i++) {
            if(node[v][i] == 1 && !check[i]) {
                System.out.print(" ");
                dfs(i);
            }
        }
    }
}
 



'개발 > Algorithm' 카테고리의 다른 글

백준 5582 : 공통 부분 문자열 풀이  (0) 2018.03.08
백준 14888 : 연산자 끼워넣기  (0) 2018.03.08
그래프의 탐색 알고리즘 : DFS, BFS  (0) 2018.03.06
백준 1019 : 책 페이지  (0) 2018.02.11
백준 1543 : 문서검색  (0) 2018.02.11
Comments