Backjoon 1260번 DFS 와 BFS

백준 알고리즘

• 1260번 DFS와 BFS

---

파이썬을 사용하였습니다.
단계별로 풀어보기 DFS와 BFS 첫번째 단계에 있는 문제입니다.

• 입력
  1. 정점의 개수, 간선의 개수, 탐색 시작할 정점을 받습니다.
  2. 시작된 정점에서 BFS,DFS를 수행한다

---

저는 파이썬의 딕셔너리를 이용해서 풀었습니다.
딕셔너리에 key에 각 정점을 저장하고 values에는 정점이 가지는 간선, 즉 이동하는 정점을 담습니다.

DFS는 Stact을 활용, BFS는 que를 활용하여 풉니다.


DFS만 간단하게 설명하면 stact이라 적혀있는 리스트에 가장먼저 시작하는 정점을 append 합니다.
이제 stact의 가장 마지막 부분을 뽑아냅니다. 뽑아낸 정점이 visit에 없으면 visit에 추가하고
뽑아낸 정점을key로 가지는 리스트 values를 정렬해서 extend합니다.
이 과정을 stact에 리스트가 빈 리스트가 되거나 visit에 모든 정점이 나타나면 종료합니다.

사진을 보면 첫 시작 정점이 3이기 때문에 visit = [3] 입니다. 이제 3을 key로 가지는 list는 [1,4]가 되고
stact에는 [4,1]가 됩니다(내림차순 정렬). 이제 1번을 추출하고 (stact=[4]) 1는 visit에 없기 때문에 visit=[3,1]가 되고
정점 1을 key로 가지는 list는 [2,3] 입니다. 이제 stact= [4,3,2] 으로 list는 extend 되고 다시 stact은 2를 추출하게 됩니다. (stact = [4,3])
2는 visit에 없습니다. visit=[3,1,2] 다시 2를 key로 가지는 리스트는 [1,5] 이제 stact은 stact=[4,3,1,5] 다음 stact은 5를 추출하고
5는 visit에 없습니다. visit=[3,1,2,5] 5는 [2,4]를 가지고 있습니다. stact=[4,3,1,2,4]를 가지는데 다시 stact은 4를 추출하게 됩니다.
추출된 4는 visit에 없기때문에 visit=[3,1,2,5,4]가 되는데 여기서 정점이 전부 등장했기 때문에 조건식에 포함되어 루프가 끝나게 되고
정답을 추출합니다.

---

정답코드

N,M,V = map(int,input().split(" "))
gragh={}
answer = []
for i in range(M):
    s,e = map(int,input().split(" "))
    if s in gragh:
        gragh[s].append(e)
    else:
        gragh[s]=[e]
    if e in gragh:
        gragh[e].append(s)
    else:
        gragh[e]=[s]

def DFS(gra,start_idx,end):
    visit=[]
    stact=[]
    stact.append(start_idx)

    while stact:
        node = stact.pop()
        if node not in visit:
            visit.append(node)
            try:
                stact.extend( sorted(gra[node],reverse=True) )
            except:
                pass
        if len(visit)==end:
            break
    return visit

def BFS(gra,start_idx,end):
    visit=[]
    que=[]
    que.append(start_idx)
    while que:
        node = que.pop(0)
        if node not in visit:
            visit.append(node)
            try:
                que.extend( sorted( gra[node]) )
            except:
                pass
        if len(visit)==end:
            break
    return visit


print(*DFS(gragh,V,N))
print(*BFS(gragh,V,N))