백준 1260번 DFS와 BFS

정보

문제 바로가기 [클릭]

난이도: Silver1

관련 개념: #그래프 이론 #그래프 탐색 #너비 우선 탐색 #깊이 우선 탐색

---

조건

시간 제한	메모리 제한
2 초	128 MB

---

문제

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

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

출력

1 2 4 3
1 2 3 4

---

예제 입출력 2

입력

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

출력

3 1 2 5 4
3 1 4 2 5

---

예제 입출력 3

입력

1000 1 1000
999 1000

출력

1000 999
1000 999

---

코드(파이썬)

import sys

sys.setrecursionlimit(10001)

def dfs(num):
    dfs_result.append(num)

    for end in graph[num]:
        if end in graph[num] and end not in dfs_result:
            check_dfs.append(end)
            dfs(end)
            check_dfs.pop()
            
def bfs(num):
    queue = [num]
    
    while queue:
        bfs_result.extend(queue)
        
        for _ in range(len(queue)):
            start = queue.pop(0)
            
            for end in graph[start]:
                if end not in bfs_result and end not in queue:
                    queue.append(end)

check_dfs = list()
queue = list()
dfs_result = list()
bfs_result = list()

n, m, s = map(int, sys.stdin.readline().split())
graph = dict(zip(range(1, n+1), [list() for _ in range(n)]))

for n1, n2 in [map(int, line.split()) for line in sys.stdin.readlines()]:
    graph[n1].append(n2)
    graph[n2].append(n1)
    
for k in graph:
    graph[k].sort()
    
dfs(s)
bfs(s)
sys.stdout.write(" ".join(map(str, dfs_result)) + "\n")
sys.stdout.write(" ".join(map(str, bfs_result)))

---

특이사항

• DFS와 BFS를 동시에 사용
• 내 코드(35,376KB, 312ms)에 비해 우수한 코드 (바로가기, 32,428KB, 108ms)와 비교

  • import sys
    from collections import deque
    
    def bfs(graph, v, visited):
        queue = deque([v])
        visited[v] = True
        while queue:
            v = queue.popleft()
            print(v, end = ' ')
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True
    
    
    def dfs(graph, v, visited):
        visited[v] = True
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                dfs(graph, i, visited)
    
    
    
    n, m, v = map(int, sys.stdin.readline().split())
    graph = [[]for i in range(n + 1)]
    for i in range(m):
        # a, b 를 입력 받은 후 그래프에 인접 노드로 넣어줌
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    # 탐색을 위해 그래프 정렬해줌
    for i in range(1, n+1):
        graph[i].sort()
    
    visited = [False]*(n+1)
    dfs(graph, v, visited)
    print()
    visited = [False]*(n+1)
    bfs(graph, v, visited)
    

  • 기존: 간선이 여러 개인 점으로 인해 if문이 복잡해지는 단점 존재
  • 개선: visited 리스트를 전달하는 방식

---

참고문헌

-