백준 알고리즘 <DFS와 BFS>

백준 알고리즘 1260번

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

1260번

그래프를 DFS로 탐색할 결과와 BFS로 탐색한 결과를 출력해라.

 

입력으로 첫 줄에 정점의 개수 N과 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에 걸쳐 간선에 대한 정보가 주어진다.

 

출력으로 첫 줄에는 DFS를 수행한 결과를 둘째 줄에는 BFS를 수행한 결과를 출력한다.

---

문제 해결

단순히 주어진 그래프를 DFS와 BFS로 탐색하면 된다.

이 문제에서는 정점 번호가 작은 것을 먼저 방문해야된다는 것을 잊지 말자.

모든 노드와 간선을 차례대로 조회하여 O(N+M)의 시간 복잡도로 문제를 해결하자.

 

bfs와 dfs에 대해 각각 start를 인자로 갖는 함수를 만들어줬다.

두 함수 모두 while문을 이용하였다.

 

dfs는 깊이 우선 탐색으로 list를 stack처럼 이용하였고 bfs는 너비 우선 탐색으로 deque를 이용하였다.

 

dfs

1) start를 stack에 넣는다.

2) stack에서 노드를 꺼낸다. 해당 노드를 방문한 적 없다면 방문처리하고 result 배열에 해당 노드를 넣는다.

   인접 노드 중 방문하지 않은 노드가 있다면 해당 노드를 stack에 넣는다.

3) stack이 빌 때까지 2)를 반복한다.

 

bfs

1) start를 queue에 넣는다.

2) queue에서 노드를 꺼낸다. 해당 노드를 방문한적 없다면 방문처리하고 result 배열에 해당 노드를 넣는다.

   인접 노드 중 방문하지 않은 노드가 있다면 해당 노드를 queue에 넣는다.

3) queue가 빌 때까지 2)를 반복한다.

---

코드

from collections import deque

n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for e in graph:
    e.sort()


def dfs(start):
    visit = [False for _ in range(n+1)]
    stack = []
    stack.append(start)
    result = []
    while stack:
        temp = stack.pop()
        if visit[temp]:
            continue
        else:
            visit[temp] = True
            result.append(temp)
            for i in range(len(graph[temp]) -1, -1, -1):
                if not visit[graph[temp][i]]:
                    stack.append(graph[temp][i])

    for i in result:
        print(i, end=" ")

def bfs(start):
    visit = [False for _ in range(n+1)]
    queue = deque()
    queue.append(start)
    result = []
    while queue:
        temp = queue.popleft()
        if visit[temp]:
            continue
        else:
            result.append(temp)
            visit[temp] = True

            for i in graph[temp]:
                if not visit[i]:
                    queue.append(i)



    for i in result:
        print(i, end=" ")

dfs(v)
print("")
bfs(v)

---

---

graph 배열은 2차원 배열이다. 각 인덱스마다 그 인덱스의 인접 노드를 가진 list를 가지고 있다.

정점번호가 작은 것을 먼저 방문해야 하기 때문에 graph 배열을 완성한 후에 정렬을 해줘야 한다.

 

또한 stack을 사용하는 dfs는 후입선출이기 때문에 정렬된 배열을 뒤에서부터 넣어줘야 작은 것이 먼저 나올 수 있다.