백준 / 1260번 DFS와 BFS / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1260번 DFS와 BFS

문제 사이트: https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

233553

88508

52532

36.731%

문제

그래프를 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 복사

1 2 4 3
1 2 3 4

예제 입력 2 복사

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

예제 출력 2 복사

3 1 2 5 4
3 1 4 2 5

예제 입력 3 복사

1000 1 1000
999 1000

예제 출력 3 복사

1000 999
1000 999

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: dfghcvb11, djm03178, doju
• 어색한 표현을 찾은 사람: doju
• 빠진 조건을 찾은 사람: pumpyboom

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

나의 풀이

제일 전형적인 BFS, DFS 탐색 문제이다. 

 

처음에 내풀이 완벽하다고 생각했는데 틀려서 당황했는데 트리에 값이 추가될때마다 정렬이 안돼서 그런 것이었음 ㅎ

        tree[a].sort()
        tree[b].sort()

해줘서 통과했다. 

import sys
from collections import deque

def dfs(node):
    global dfs_visited
    global dfs_result
    
    dfs_result.append(node)

    for i in tree[node]:
        if dfs_visited[i] == 0:
            dfs_visited[i] = 1
            dfs(i)
            
def bfs(v):
    queue = deque()
    queue.append(v)
    
    bfs_visited = [0 for i in range(n+1)]
    bfs_visited[v] = 1
    bfs_result = []
    
    while queue:
        node = queue.popleft()
        bfs_result.append(node)
        for i in tree[node]:
            if bfs_visited[i] == 0:
                bfs_visited[i] = 1
                queue.append(i)
    for i in bfs_result:
        print(i, end = " ")
    
if __name__ == "__main__":
    input = sys.stdin.readline
    n,m,v = map(int,input().split()) # 정점, 간선, 탐색시작번호
    tree = {i:[] for i in range(1,n+1)}

    ### DFS ###
    dfs_visited = [0 for i in range(n+1)]
    dfs_result = []
    for _ in range(m):
        a,b = map(int,input().split())
        tree[a].append(b)
        tree[b].append(a)
        tree[a].sort()
        tree[b].sort()
    
    dfs_visited[v] = 1
    dfs(v)
    for i in dfs_result:
        print(i, end = " ")
    print()
    ### BFS ###
    bfs(v)

확실히 리스트로 방문처리 확인하는 걸 추가해서 시간이 빨라진 거 같다 ㅎㅎ

 

다른 풀이

이건 내 코드에서 더 빠른 40ms 정도 걸린 문제.. 확실히 잘 정리되어서 보기도 좋은듯

# DFS와 BFS
import sys
input = sys.stdin.readline

def dfs(n):
    visited[n] = True
    dfs_list.append(n)
    for w in sorted(adj_list[n]):
        if not visited[w]:
            dfs(w)


def bfs(n):
    visited[n] = True
    queue = [n]
    while queue:
        v = queue.pop(0)
        bfs_list.append(v)
        for w in sorted(adj_list[v]):
            if not visited[w]:
                visited[w] = True
                queue.append(w)


N, M, V = map(int, input().split())
adj_list = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    adj_list[a].append(b)
    adj_list[b].append(a)

dfs_list = []
bfs_list = []

dfs(V)
visited = [False] * (N + 1)
bfs(V)

print(*dfs_list)
print(*bfs_list)

---

※ 알아야 할 것

- 방문처리는 리스트로 야무지게