[백준]_1260번 : DFS와 BFS(파이썬 and C언어)

1260번: DFS와 BFS

INDEX

1. 그래프 탐색

2. 전략(파이썬)

3. 전략(C언어)

1. 그래프 탐색

어떤 정점들이 서로 간선으로 연결되어 있다. 이것을 그래프라고 한다. 그래프 탐색이 초반에 까다롭게 느껴지는 점은 바로 방문했던 정점을 다시 방문할 필요가 없다는 사실이다.  이제 이것을 코드로 어떻게 처리하냐는 나중의 문제이고, 그래프 탐색에는 크게 두 가지 방법이 있고 이번 문제에서는 그것들에 대해 묻고 있다. 

 

---

 

첫 번째는 DFS(Depth-First Search)이다. 

 

시작점에서 처음 선택한 브랜치에서 정점을 방문한 후 다음 형제 노드로 바로 넘어가지 않고 단말 노드가 나올 때 까지 탐색한다. 방문이 완벽이 이루어지고 나서야 다음 브랜치로 넘어간다. 각 노드가 연결되어 있는 노드들의 정보를 graph에 담고 재귀함수로 진행하면서 방문한 노드는 visited에 기록하는 것이 가장 일반적이다. 항상 최적의 해를 찾는다는 보장은 없지만 BFS보다 간단하고 목표 노드가 깊이 있을 때 찾기 빠른 장점이 있다.

 

 

두 번째는 BFS(Breadth-First Search)이다.

 

간선 하나만 집요하게 탐색하는 DFS와는 다르게 형제를 모두 방문하기 전까지는 절대 노드의 레벨을 높이지 않는다. DFS와 마찬가지로 graph와 visited를 생성해야 하지만 큐를 이용해서 탐색을 진행한다는 것이 독특한 점이다. 큐는 한쪽으로만 입력(enqueue)이 가능하고 다른 쪽으로만 출력(dequeue)이 가능한 자료구조이다. DFS보다는 검색 속도가 빠르고 그래프의 길이가 얕을수록 빠르지만 깊이가 깊어질수록 메모리가 많이 필요하다는 단점이 있다.

 

파이썬과 C언어로 모두 짜보니 둘의 논리가 살짝 다름을 깨달아 두 언어를 분리해서 풀어보겠다. 

 

2. 전략(파이썬)

먼저 노드들이 어떤 노드들과 접점이 있는지 파악하게 해주는 graph를 생성해보자. 가능한 노드의 최고 번호는 N이고 인데스적 특성 때문에 graph의 선언은 아래와 같다.

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

따라서 정점2에 대해 접근하고 싶으면 graph [2]로 접근하면 돼서 (만약 N+1이 아니라 N으로 적었으면) graph [1]로 접근해야 하는 것보다 더 직관적으로 이해하기 쉽다. 이제 예제 입력1을 사용해 보자.

 

1과 2를 a와 b변수로 받아 보자. 노드 1은 노드 2와 만나고 노드 2는 노드 1과 만나기 때문에 graph [1]에는 2가, graph [2]에는 1이 추가되어야 한다. 이제 이것을 모든 입력에 대해 해 주기 위해서 graph 입력 코드는 다음과 같다.

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

이제 예제 입력 1을 모두 입력하고 나면 graph는 [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]이 저장되어 있을 것이다.

 

그래프 탐색을 시작하기 앞서 이 문제 특유의 조건 때문에 추가 작업을 해주어야 한다.

"단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"

따라서 graph안에 있는 리스트 내부를 각각 정렬해주어야 한다.

 

정렬을 .sort()로 대충 끝내주고 나면 먼저 DFS부터 시작해 보자.

 

(1) DFS

DFS 전용 visited 리스트를 만들어주고 재귀적으로 실행해 준다.

visited = [0] * (N+1)
def dfs(node):
    print(node, end=' ')
    visited[node]=1 # node를 방문한 적이 있음을 흔적을 남김. 이 시점 이후로 node를 방문할 기회는 없음
    for num in graph[node]:
        if visited[num]==0: # 방문한 흔적이 없는 노드(num)이면 
            dfs(num) # 정점 num으로 들어가서 깊이 탐색

이렇게 되면 visited에 dfs에 의해 방문한 정점들이 쌓이게 된다. 이 내용물을 출력해 주면 dfs출력 해결!

 

(2) BFS

visited를 초기화(visited= [0]*(N+1) ) 시켜준다. 아까의 visited와 약간 다른 방법으로 초기화해준 이유는 단순히 방문한 노드들의 번호를 빈 배열에 저장하는 것보다 visited에서 인덱스로 접근하는 것이 BFS방법에서는 더 빨라서이다. 재귀 대신에 큐를 사용할 것이기 때문에 코드 상단에 from collections import deque를 해주고 난 뒤 아래의 코드를 적어주면 된다.

def bfs(node):
    visited = [0] * (N + 1)
    q = deque([node])
    while q: # 큐가 완전히 비워지면 탐색 종류
        target = q.popleft() # 가장 최근에 들어온 노드를 target으로 옮기기
        print(target, end=' ') # 출력
        visited[target] = 1 # 방문했으니까 1로 만들기
        for num in graph[target]: # target에 등록 되어 있는 자식 노드들 중간 이탈 없이 검사
            if visited[num] == 0: # 방문한적이 없으면
                visited[num] = 1
                q.append(num) # 추후 탐색 후보로 등록
bfs(start_node)

따라서 전체 코드는 아래와 같다.

from collections import deque
import sys

input = sys.stdin.readline

N, M, start_node = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]
for i in range(1, N + 1):
    graph[i] = sorted(graph[i])
visited = [0] * (N + 1)

def dfs(node):
    print(node, end=' ')
    visited[node]=1
    for num in graph[node]:
        if visited[num]==0:
            dfs(num)
dfs(start_node)
print()

def bfs(node):
    visited = [0] * (N + 1)
    q = deque([node])
    while q:
        target = q.popleft()
        print(target, end=' ')
        visited[target] = 1
        for num in graph[target]:
            if visited[num] == 0:
                visited[num] = 1
                q.append(num)
bfs(start_node)

3. 전략(C언어)

파이썬에서 그래프가 서로 연결된 정점들을 저장하는 역할을 했다면, C에서는 동적 배열이 아닌 최대 크기(1000)만큼 먼저 선언한 후 의미가 있는 노드(방문된 노드,  연결된 노드)를 1로 표시하고 나머지를 0으로 표시하자.

 

또한 파이썬에서는 큐를 사용해 줬지만 이번에는 큐를 가장한 배열을 사용해 보자. 연결 리스트로 실제 큐를 구현해 버리면 코드가 너무 복잡해지기 때문에 생각해 낸 방법이다.

 

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 1001

int graph[MAX_SIZE][MAX_SIZE] = {0};
int visited[MAX_SIZE] = {0};
int queue[MAX_SIZE] = {0};

void dfs(int, int);
void bfs(int, int);
void solve_1260();

int main() {
    solve_1260();
    return 0;
}

void solve_1260() {
    int N, M, start_node;
    scanf("%d %d %d", &N, &M, &start_node);
    int a, b;
    for (int i = 0; i < M; ++i) {
        scanf("%d %d", &a, &b);
        graph[a][b] = 1;
        graph[b][a] = 1;
    }
    dfs(N, start_node);
    memset(visited, 0, sizeof(int) * (N + 1));
    printf("\n");
    bfs(N, start_node);
}

void dfs(int N, int node) {
    visited[node] = 1;
    printf("%d ", node);
    // 1001까지 갈 수 있지만 앞서 입력한 N이 최대 숫자이므로...
    for (int i = 1; i <= N; ++i) {
        if (graph[node][i] && !visited[i])
            dfs(N, i);
    }
}

void bfs(int N, int node) {
    int front = -1;
    int rear = -1;
    int pop;
    printf("%d ", node);
    visited[node] = 1;
    queue[++rear] = node;
    while (front < rear) {
        pop = queue[++front];
        for (int i = 1; i <= N; ++i) {
            if (graph[pop][i] && !visited[i]) {
                printf("%d ", i);
                visited[i] = 1;
                queue[++rear] = i;
            }
        }
    }
}