[백준 1260] [dfs/bfs] BFS와 DFS ❗

💻 백준 1260번 [BFS와 DFS]

1260번: DFS와 BFS

풀이)

# 최종제출
from collections import deque
n,m,v = map(int,input().split())
input_lst = sorted([list(map(int,input().split())) for _ in range(m)], key = lambda x : (x[0],x[1]))
edge_lst = [[] for _ in range(n+1)]
for v1,v2 in input_lst :
    edge_lst[v1].append(v2)
    edge_lst[v2].append(v1)
    
visited = [0]*(n+1)
dfs_lst = []
def dfs(v,dfs_lst) :
    # 1. 방문한 노드인지 확인
    if visited[v] == 0 :
        dfs_lst.append(v) 
        # 방문처리
        visited[v] = 1
        # 2. 인접한 노드 순회
        for v2 in sorted(edge_lst[v]) :
            dfs(v2,dfs_lst)
    return dfs_lst
print(*dfs(v,dfs_lst)) 

visited = [0]*(n+1)
q = deque()  
# 첫 노드 큐삽입 & 방문처리
q.append(v)
visited[v] = 1
bfs_lst = [v]
while 1 :
    for v2 in sorted(edge_lst[v]) : 
        if visited[v2] == 0 :
            q.append(v2)
            bfs_lst.append(v2)
            visited[v2] = 1
    if len(q) == 0:
        break
    v = q.popleft() 

print(*bfs_lst)

메모리	시간	언어	코드길이
35284KB	616ms	Python 3	990B

 

처음에 실수했던 포인트는 edge_lst를 만들때 인접노드들 리스트가 sorting이 안되어 있던 것

그래서 dfs/bfs 과정 안에서 인접노드 확인할 때 sorted() 함수를 이용하여 sorting을 하고 인접노드들을 값이 작은 것부터 확인해나가는 과정을 거쳤다

이를 확인할 수 있게 도와준 반례는 다음과 같다

# input 
10 10 4
5 4
6 4
6 8
8 9
1 10
2 10
10 3
8 2
1 7
4 10

# output
4 5 6 8 2 10 1 7 3 9
4 5 6 10 8 1 2 3 9 7

 

BFS와 DFS 구현하기. 기본 중에 기본이니 이것부터. ‼