반응형

문제


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


입력


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



백준에서 Queue로 분류가 되어있는 문제입니다. 이 문제를 풀때 Queue로 분류되어 있다고 Queue만 사용한다면 문제를 푸는데 조금 힘들 수 있습니다.

DFS(깊이 우선 탐색)의 경우 Stack, BFS(너비 우선 탐색)의 경우 Queue를 사용해서 풀면 간단하게 구현이 가능합니다.


DFS의 경우 Stack을 사용하는데, 각 노드를 방문하고 자식노드를 찾으러 가야하는 경우에 Stack의 현재 노드를 push해줍니다. 이후에 다시 이 노드로 돌아오게 되는 경우에 이 Stack에 저장된 값을 가지고 이 노드로 돌아와서 나머지 자식노드들을 탐색 할 수 있게 저장하는 것입니다.


BFS의 경우 Queue를 사용하는데, 노드를 방문할때마다 Queue에 저장을 합니다. 즉 현재 노드의 자식노드들을 전부 Queue에 push를 합니다. 모든 자식 노드를 push를 하였으면 Queue에서 pop해서 queue의 넣은 자식노드들 중 가장 먼저 넣었던 노드 번호를 꺼내오고 그 노드의 자식 노드를 전부 Queue의 넣습니다. 위 과정을 반복하면 너비 우선 탐색으로 모든 노드들을 탐색 할 수 있습니다.


코드

아래 코드의 경우 이전에 백준 문제를 풀며서 구현해놓은 Queue와 Stack을 사용하여 문제를 풀었습니다. Queue와 Stack의 push, pop이 어떤 상황에 쓰이는지 확인해보시고 문제를 풀면 도움이 될것 같네요. 

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0) if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0] if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1] if self.size() != 0 else -1
 
class Stack:
    def __init__(self):
        self.list = []
 
    def push(self, num):
        self.list.append(num)
 
    def pop(self):
        if self.size() == 0:
            return -1
        return self.list.pop()
 
    def size(self):
        return len(self.list)
 
    def empty(self):
        return 1 if len(self.list) == 0 else 0
 
    def top(self):
        return self.list[-1] if self.size() != 0 else -1
 
node, edge, start = map(int, input().split())
 
#graph
graph =  [[0 for cols in range(node)]for rows in range(node)]
for _ in range(edge):
    source, target = map(int, input().split())
    graph[source-1][target-1] = 1
    graph[target-1][source-1] = 1
 
#dfs
stack = Stack()
dfs_visited_flag = [0 for clos in range(node)]
current_node = start-1
output = []
while(True):
    visit_count = 0
    if current_node + 1 not in output:
        output.append(current_node + 1)
        dfs_visited_flag[current_node] = 1
    for i in range(node):
        if graph[current_node][i] == 1 and dfs_visited_flag[i] != 1:
            stack.push(current_node + 1)
            current_node = i
            visit_count += 1
            break
    if visit_count == 0:
        current_node = stack.pop() - 1
 
    if current_node < 0:
        break
 
print(" ".join(str(x) for x in output))
 
#bfs
queue = Queue()
bfs_visited_flag = [0 for clos in range(node)]
queue.push(start)
current_node = start-1
bfs_visited_flag[current_node] = 1
output = []
while(True):
    for i in range(node):
        if graph[current_node][i] == 1 and bfs_visited_flag[i] != 1:
            queue.push(i+1)
            bfs_visited_flag[i] = 1
    output.append(queue.pop())
    current_node = queue.front()-1
    if current_node < 0:
        break
 
print(" ".join(str(x) for x in output))
 
cs


반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현  (0) 2019.01.13
[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.08

+ Recent posts

티스토리툴바