[알고리즘][Python] 백준 1260 DFS와 BFS 문제 풀이

문제 출처 :www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

문제 해석 : 큐와 스택을 이용해서 방문하는 노드를 순서대로 출력하는 문제이다. 기본적인 조회이므로 자신이 원하는 구조로 자료를 정리한 다음 방문처리 해주면 된다.

 

문제 풀이 :  각각 노드에서 이동가능한 노드를 표시하는 graph를 선언하고 방문 된 적이 있는지 체크하는 visited 를 이용해서 방문 처리를 실행한다. 여기서 주의할 점은 낮은 번호 순서로 방문 할 수 있도록 정렬을 실시해야 한다는 것이다.

 

---

풀이 코드

N, M, V = map(int, input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)


def BFS(graph, visited):

    Q = []
    temp = []
    for element in graph[V]:
        temp.append(element)
    temp.sort()
    for element in temp:
        Q.append(element)
    visited[V] = 1
    print(V, end= " ")
    while Q:
        ne = Q.pop(0)

        if visited[ne] == 0:
            visited[ne] = 1
            print(ne, end = " ")

            temp = []
            for element in graph[ne]:
                if visited[element] == 0:
                    temp.append(element)
            temp.sort()
            for element in temp:
                Q.append(element)

def DFS(graph, visited):

    stack = []
    temp = []
    for element in graph[V]:
        temp.append(element)
    temp.sort(reverse = True)
    for element in temp:
        stack.append(element)
    visited[V] = 1
    print(V, end=" ")

    while stack:
        ne = stack.pop()

        if visited[ne] == 0:
            visited[ne] = 1
            print(ne, end = " ")
            temp = []
            for element in graph[ne]:
                if visited[element] == 0:
                    temp.append(element)
            temp.sort(reverse= True)
            for element in temp:
                stack.append(element)

visited = [0] * (N+1)
DFS(graph, visited)
print()
visited = [0] * (N+1)
BFS(graph,visited)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.