그래프 연습 (2) - DFS와 BFS (백준 1260)

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

1260번: DFS와 BFS

 

그래프와 DFS개념, BFS개념을 연습하기 아주 좋은 문제인 것 같다. (난이도: 실버 2)

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

풀이

먼저 아래 링크에서 설명한 그래프 표현 방식 중 인접행렬 방식을 사용하겠습니다.

2023.11.08 - [Algorithm] - 그래프 연습 (1) - 인접 행렬과 인접 리스트

그래프 연습 (1) - 인접 행렬과 인접 리스트

 

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

graph_matrix = [[0 for _ in range(N+1)] for _ in range(N+1)] # 인접행렬 초기화

for _ in range(M):
    v1, v2 = map(int, input().split())
    graph_matrix[v1][v2] = 1
    graph_matrix[v2][v1] = 1

visited = [False for _ in range(N+1)] # 방문처리

visited는 리스트로 노드의 번호가 곧 visited의 인덱스가 된다. 노드의 번호는 1부터 시작되므로 0~N까지 생성한다.

노드를 방문하면 해당 노드 번호 V를 True로 바꿔준다. 즉 visited[V] = True를 진행한다.

---

DFS

DFS의 개념은 다른 블로그에서 설명이 아주 잘 되어있다. 아무래도 재귀형태로 이루어져 있기 때문에 처음 이해하는데 버거운 개념이다. DFS의 코드를 살펴보자.

def dfs(V, visited):
    visited[V] = True
    print(V, end=' ')

    for i in range(1, len(graph_matrix[V])):
        if graph_matrix[V][i] == 1 and not visited[i]:
            dfs(i, visited)
            
dfs(V_start, visited)

인자로 받은 노드 V를 방문처리 (visited[V] = True) 를 진행하고 해당 노드를 출력한다.

 

그리고 해당 노드의 행에서 값이 1인 것은 곧 해당 노드와 연결된 노드들의 리스트이다.

따라서 모두 순회해서 값이 1이면서 방문을 하지 않았을 경우에, 해당 노드를 인자로 다시 dfs함수를 호출한다.

---

BFS

BFS의 코드를 살펴보자. 재귀(스택)가 아닌 큐로 구현이 되며 가장 먼저들어온 값을 빼내기 위해 deque를 사용하는 알고리즘이다. deque를 사용하는 이유는 일반적인 리스트에서 .pop(0)으로 맨 앞의 인자를 뺄 때, 그 뒤에 있는 인자들을 한칸씩 왼쪽으로 움직여야하므로 O(n)의 시간복잡도가 소요되지만 deque는 O(1)로 진행할 수 있다. 값이 적던 크던 그냥 모두 deque를 쓰자!

from collections import deque

def bfs():
    q = deque([V_start]) # 시작값부터 q에 넣기
    visited = [False for _ in range(N+1)] # 방문 처리 리스트 (dfs와 동일)
    
    while q:
        V = q.popleft() # q에 먼저들어온것 부터 빼내서
        visited[V] = True # 방문처리를 하고
        print(V, end=' ') # 출력
        
        for i in range(1, len(graph_matrix[V])): # dfs와 마찬가지로 순회
            if graph_matrix[V][i] == 1 and not visited[i]: # dfs와 같은 조건
                visited[i] = True # 방문처리하고
                q.append(i) # 여기서 방문 가능한 노드를 q에 모두 넣는다는 것에서 너비우선이 됨!
                			# dfs는 방문이 가능하자마자 해당 노드로 이동하므로 깊이우선이 됨!

주석을 통해 코드 설명을 진행했다. 위에서 말한대로 q에 append하는 과정이 해당 노드에서 방문이 가능한 노드를 모두 q에 넣으므로 너비우선이 되는거고, dfs는 방문이 가능한 노드를 찾자마자 해당 노드로 이동하기 때문에 깊이 우선이 된다.

 

전체코드

방문할 수 있는 노드가 여러 개면 노드번호가 낮은것부터 순회하라고 했으니 for문의 range가 1부터 증가하므로 가장 먼저 발견된 곳이 결국 방문 대상이다. 따라서 더욱 간단한 문제이다.

from collections import deque

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

graph_matrix = [[0 for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    v1, v2 = map(int, input().split())
    graph_matrix[v1][v2] = 1
    graph_matrix[v2][v1] = 1

visited = [False for _ in range(N+1)]

def dfs(V, visited):
    visited[V] = True
    print(V, end=' ')

    for i in range(1, len(graph_matrix[V])):
        if graph_matrix[V][i] == 1 and not visited[i]:
            dfs(i, visited)

def bfs():
    q = deque([V_start])
    visited = [False for _ in range(N+1)]
    
    while q:
        V = q.popleft()
        visited[V] = True
        print(V, end=' ')
        
        for i in range(1, len(graph_matrix[V])):
            if graph_matrix[V][i] == 1 and not visited[i]:
                visited[i] = True
                q.append(i)
                
dfs(V_start, visited)
print()
bfs()

 

- 끝 -