(파이썬)백준 알고리즘 1260번 DFS와 BFS

백준 알고리즘 저지 1260번 문제 (https://www.acmicpc.net/problem/)

 

 

DFS(깊이 우선 탐색) BFS(너비 우선 탐색)의 구현

정점과 노드수 출발점과 노드가 주어지고 각 탐색결과를 출력

 

 

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
·¬
visit={·}¬
load={·}¬
N,·M,·V·=·map(int,·input().split())¬
¬
for·i·in·range(M):¬
····fromN,·toN·=·map(int,·input().split())¬
····visit[fromN]=0¬
····visit[toN]=0¬
····if·load.get(fromN)==None:¬
········load[fromN]=[·]¬
····if·load.get(toN)==None:¬
········load[toN]=[·]¬
····load[fromN].append(toN)¬
····load[toN].append(fromN)¬
¬
for·a·in·load:¬
····load[a].sort()¬
····¬
way=[]¬
def·DFS(startV):¬
····way.append(startV)¬
····visit[startV]=1·¬
····for·toN·in·load.get(startV):¬
········if·visit.get(toN)·==·0:¬
············DFS(toN)¬
¬
bfsWay=[]¬
def·BFS(startV):#1¬
····flag=0¬
····for·toN·in·load.get(startV):¬
········if·visit.get(toN)==0:¬
············bfsWay.append(toN)¬
············visit[toN]=1¬
············flag=1¬
····if·flag!=0:¬
········for·nextN·in·bfsWay:¬
············BFS(nextN)¬
¬
DFS(V)¬
¬
for·i·in·visit.keys():#visit초기화¬
····visit[i]=0¬
bfsWay.append(V)¬
visit[V]·=·1¬
BFS(V)¬
¬
result=''¬
for·i·in·way:¬
····result+=str(i)+'·'¬
print(result[:len(result)-1])¬
result=''¬
for·i·in·bfsWay:¬
····result+=str(i)+'·'¬
print(result[:len(result)-1])¬
¶
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

 

이건 저번거 코드 안보고 다시 짜본건데 제대로 작동하는데 계속 에러가 난다고 뜨길래 삽질좀 했더니 load를 sort 안해놔서 그렇더라 원래 트리가 1 2 3 4 순서대로 배치가 되나? 그냥 라벨일 뿐 아니였나..

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
·¬
visit·=·{}¬
visit2·=·{}¬
load·=·{}¬
result·=·[]¬
¬
N,M,V·=·map(int,input().split())¬
#·간선수¬
¬
for·i·in·range(M):¬
····start,·end·=·map(int,input().split())¬
¬
····visit[start]·=·visit.get(start,0)¬
····visit[end]·=·visit.get(end,·0)¬
····if·load.get(start)==None:¬
········load[start]=[]¬
····if·load.get(end)·==·None:¬
········load[end]·=·[]¬
····load[start].append(end)¬
····load[end].append(start)¬
#print(visit)¬
#print(load)¬
for·a·in·load:¬
····load[a].sort()¬
visit2=visit.copy()¬
¬
def·DFS(visit,·load,·start):¬
····if·visit[start]==1:¬
········return¬
····visit[start]=1¬
····result.append(start)¬
····for·next·in·load.get(start,[]):¬
········DFS(visit,load,next)¬
¬
DFS(visit,load,V)¬
#print(result)¬
r=''¬
for·s·in·result:¬
····r+=str(s)+'·'¬
print(r.rstrip())¬
¬
result=[]¬
¬
def·BFS(visit,load,stack):¬
····tmp·=·[]¬
····for·n·in·stack:¬
········if·visit[n]·==·1:¬
············continue¬
········visit[n]=1¬
········result.append(n)¬
········for·nn·in·load.get(n,[]):¬
············if·visit[nn]·!=·1·and·nn·not·in·tmp:¬
················tmp.append(nn)¬
¬
····if·len(tmp)==0:¬
········return¬
····BFS(visit,·load,tmp)¬
¬
BFS(visit2,load,[V])¬
#print(result)¬
¬
r=''¬
for·s·in·result:¬
····r+=str(s)+'·'¬
print(r.rstrip())¬
¶
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX