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

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

 

 

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

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

 

 

 
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])

 

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

 
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())