DFS 및 BFS 기본 응용 문제 _ 방문 순서 출력

DFS 및 BFS 기본 개념을 알았다고 해도, 막상 응용문제를 풀어보려고 하니 이해하기가 쉽지 않네요.

가장 개념에 가까운 문제부터 풀어봅시다.

1. 문제와 문제 조건 파악하기

문제:

N개의 정점(Vertex)이 리스트 형태로 주어진다. 다음과 같이 그래프가 주어져 있을 때, DFS/ BFS 알고리즘을 이용하여, 방문 순서를 차례대로 저장한 리스트를 반환해라.

 

주어진 리스트

조건:

- 시작 노드는 1

- DFS / BFS 탐색은 주어진 간선 리스트 내의 원소 순서로 할 것

2. 문제 풀어보기 _ DFS 알고리즘 결과

문제를 해결하기 위해 제시한 예시 코드는 다음과 같습니다.

 

예시 코드:

List = [[0,1,1,1],[0,0,0,1],[0,0,0,1],[0,0,0,0]]

def DFS(List,vert,vlist,order):
    vlist[vert]=True
    if vert not in order:
        order.append(vert)
    for v in range(len(List)):
        if List[vert-1][v]==1 and v>vert-1:
            DFS(List,v+1,vlist,order)
    return order

def Travel(List):
    vlist={}
    order=[]
    V=[1,2,3,4]
    for v in V:
        if v not in vlist:
            DFS(List,v,vlist,order)
    return order

* 위 코드는 양방향이어도 동일한 결과를 얻는 DFS 코드이다.

 

코드 결과:

DFS 기본 개념 문제

3. 문제 풀어보기 _ BFS 알고리즘 결과

문제를 해결하기 위해 제시한 예시 코드는 다음과 같습니다.

 

예시 코드:

List = [[0,1,1,1],[0,0,0,1],[0,0,0,1],[0,0,0,0]]

def BFS(List,vert,vlist,order):
    vlist[vert]=True
    if vert not in order:
        order.append(vert)
    for v in range(4):
        if List[vert-1][v]==1 and v+1 not in order:
            order.append(v+1)
    return order

def Travel(List):
    vlist={}
    order=[]
    V=[1,2,3,4]
    for v in V:
        if v not in vlist:
            BFS(List,v,vlist,order)
    return order

 

BFS 기본 개념 문제