1260번. DFS와 BFS

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

 

 

딕셔너리를 이용한 DFS와 BFS 구현하기 문제이다.

인접 행렬(이중 리스트)이 아닌 딕셔너리를 사용한 이유는, 정점은 많은데 간선이 적은 경우 시간 및 메모리 낭비를 피하기 위함이다. 예를 들어 정점은 1000개인데 간선은 1개일 때, 인접 행렬의 0, 1로 이를 표현한다고 생각해보자. 0들로 채워진 수많은 값들은 버려질 것이다. 그리고 탐색할 때도 오래 걸릴 것이다.

따라서 파이썬을 통해 DFS 및 BFS를 구현할 때는 {시작정점:도착정점}으로 이루어진 딕셔너리를 사용하는 것이 좋다고 판단했다.

 

단순한 것 같지만 인터넷에서 BFS, DFS 구현 코드를 배워다 그대로 쓰면 틀리는 문제이다.

문제에 있는 조건 중 신경써야 할 것은 

자식이 여러 개라면 작은 것부터 방문해야 한다는 것이고,

또한 간선이 없는 그래프일 수도 있다 (ex: 입력이 1 0 1 인 경우) 는 것이다.

 

(참고..쓰다보니 단어를 혼합해서 썼는데 정점=노드, 인접=자식 의 의미로 썼다.)

먼저 데이터 삽입부부터 보자.

n, m, v = map(int, sys.stdin.readline().split())  # n=정점 갯수, m=간선 갯수, v=시작점
graph = {}  # 인접 노드들을 표시한 딕셔너리
for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    if start in graph:
        if end not in graph[start]:
            graph[start].append(end)
    elif start not in graph:
        graph[start] = [end]
    if end in graph:
        if start not in graph[end]:
            graph[end].append(start)
    elif end not in graph:
        graph[end] = [start]

for vertex in graph.keys():
    graph[vertex].sort()

1) 문제에 있는 알파벳을 그대로 사용했다.

2) graph는 자식 노드(인접 노드)들을 표시한 딕셔너리이다.

3) 간선 갯수만큼 for문을 돌린다. 노드 갯수만큼이 아니다. 입력으로 주어지는 1 3, 2 3 등은 간선을 표시한 거다.

4) start와 end는 시작 정점, 도착 정점을 의미한다. 사실 시작과 도착의 의미는 없지만 1 3에서 앞에 있는 숫자가 시작, 뒤에 있는 숫자가 도착이라고 임의로 정한거다. 

5) 먼저 start라는 정점이 graph에 이미 key로 존재하는지 확인하고, 있다면 거기에 end를 추가한다. 

6) graph[start]에 이미 end라는 정점이 있는지 살피는 이유는 두 정점 사이에 여러 간선이 있을 수 있기 때문이다. 입력이 2 5, 5 2 와 같이 들어왔을 때 굳이 자식들이 중복되서 들어가지 않게 하기 위함이다.

8) 만약 graph에 start라는 key가 없다면, 그 key를 추가하고 end를 리스트화해서 value로 넣는다.

10~14) end라는 정점에 대해서 같은 작업을 반복해준다. 무방향 그래프이므로, 1 3이 주어진다면 1의 자식은 3이며 3의 자식은 1이기 때문이다.

16~17) 입력이 오름차순으로 순차적으로 주어진다는 보장이 없으므로 정렬해준다.

 

설명은 엄청 긴데, 리스트를 사용해서 중복을 제거하며 인접 노드들을 (양방향으로) 추가해줬다고 생각하면 된다.

graph는 {1: [2, 3], 2: [1], 3: [1, 4], 4: [3]} 이런 모양이다.

인접 노드를 추가할 때 중복을 피하는 작업을 하면서까지 굳이 set을 안 쓰고 리스트를 쓴 이유는 

나중에 인접한 노드가 여러 개일 경우 크기가 작은 것부터 방문해야 하는데, set은 순서가 없는 자료형이기 때문이다.

 

아래로는 진짜 구현부다.

 

 

 

재귀를 이용한 DFS

def DFS_recursion(start, visited):
    visited.append(start)
    if start in graph:
        for child in graph[start]:
            if child not in visited:
                DFS_recursion(child, visited)
    return visited
    
ret = []
Print(DFS_recursion(v, ret))

좀더 이해하기 쉬운 재귀를 이용한 방식이다. 먼저 문제에서 정해준 v라는 시작 정점으로 호출한다.

2) 해당 정점을 방문한 리스트에 추가한다.

3) 해당 정점이 인접 노드가 있다면! (무인도처럼 떨어져 있는 정점이 있을 수 있다. 이런 경우에 해당 정점은 graph에 등장하지 않는다. 이 if문이 없다면 런타임 에러가 날 수 있다)

4) 그 인접 노드들을 child로 하나하나 가지고 와서 방문하지 않았을 경우, 그 child로 다시 이 함수를 시작한다.

이 함수는 자식 노드들을 방문하는 함수이므로, 재귀 함수를 호출할 때마다 자식 노드->자식의 자식 노드->자식의 자식의 자식 노드 순으로 방문하게 된다.

하지만 이와 같이 재귀로 DFS를 구현할 경우 이해하기에는 직관적이지만 속도가 느려질 수 있고 최대 재귀 깊이에 따라서 에러가 날 수 있다.

 

 

 

Stack를 이용한 DFS

def DFS_stack(start):
    visited = []
    stack = []
    stack.append(start)

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            if node in graph:
                stack.extend(sorted(graph[node], reverse=True))
    return visited
    
 Print(DFS_stack(v))

 스택을 이용한 방식은 stack이라는 리스트를 따로 만들어줘야 한다. 스택을 이용한 방식에서는 이 함수를 또다시 호출하는 일은 없을 것이므로 visited를 함수 밑에서 생성해도 된다.

4) 먼저 시작 정점을 stack에 추가한다.

6) stack이 비어 있지 않을 때까지 진행한다.

7~8) stack에서 노드를 하나 꺼내서, 아직 방문하지 않았다면 방문한 리스트에 추가하고

9) 그 노드가 인접 딕셔너리에 key로 존재한다면, 즉 인접 노드들을 가지고 있다면! (인접 노드가 0일 수 있음)

10) stack 리스트에 그 인접 노드들을 모두 추가해주되, 역순으로 추가한다. 그 이유는 스택은 마지막에 들어온 것이 먼저 나가는데, 현재 노드가 1이고 앞으로 추가할 노드들이 2, 3, 4라고 한다면 4, 3, 2 순으로 추가해줘야 2부터 방문할 것이기 때문이다.

이게 왜 DFS이냐 하면, 스택에 추가되서 방문되는 순서를 생각해보자. 시작 노드가 1이고 그 자식 노드가 2, 3, 4라고 한다면 스택에 4, 3, 2 순으로 들어올 것이다. 그 다음 반복문에서 2를 pop 하고 방문한 뒤 2의 자식들을 또 stack에 추가하고, 그것들을 방문하고...생각해보면 DFS이다.

 

 

 

리스트를 사용한 BFS

def BFS_list(start):
    visited = []
    queue = []
    queue.append(start)

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            if node in graph:
                queue.extend(graph[node])  # node의 자식 노드 추가
    return visited
    
Print(BFS_list(v))

리스트보다는 collections의 deque를 사용하는 것이 빠르지만, 이해를 위해서 일단 리스트를 사용했다.

BFS는 DFS 스택 버전과 거의 비슷하다. 달라지는 것은 7번줄의 pop(0)이다.

앞에서부터 노드를 빼서 방문하겠다는 것이다. 

처음에는 시작 노드의 자식 노드들을 방문했다가, 그 자식들의 자식들을 맨 뒤에 추가하고, 앞에서부터 순차적으로 방문하니 BFS가 되는 것이다.

 

 

 

Collections의 Deque를 사용한 BFS

import collections

def BFS_queue(start):
    visited = []
    queue = collections.deque()
    queue.append(start)

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            if node in graph:
                queue.extend(graph[node])
    return visited
    
Print(BFS_queue(v))

pop(0) 는 O(N)

deque의 popleft() 는 O(1)이다. 큐를 파이썬에서 사용하려면 이것을 써야한다고 한다.

 

 

 

 

코드 전문

import sys
import collections


def DFS_recursion(start, visited):
    visited.append(start)
    if start in graph:
        for child in graph[start]:
            if child not in visited:
                DFS_recursion(child, visited)
    return visited


def DFS_stack(start):
    visited = []
    stack = []
    stack.append(start)

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            if node in graph:
                stack.extend(sorted(graph[node], reverse=True))
    return visited


def BFS_list(start):
    visited = []
    queue = []
    queue.append(start)

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            if node in graph:
                queue.extend(graph[node])  # node의 자식 노드 추가
    return visited


def BFS_queue(start):
    visited = []
    queue = collections.deque()
    queue.append(start)

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            if node in graph:
                queue.extend(graph[node])
    return visited


def Print(lst):
    for i in lst:
        print(i, end=' ')
    print("")


n, m, v = map(int, sys.stdin.readline().split())  # n=정점 갯수, m=간선 갯수, v=시작점
graph = {}  # 인접 노드들을 표시한 딕셔너리
for i in range(m):
    start, end = map(int, sys.stdin.readline().split())
    if start in graph:
        if end not in graph[start]:
            graph[start].append(end)
    elif start not in graph:
        graph[start] = [end]
    if end in graph:
        if start not in graph[end]:
            graph[end].append(start)
    elif end not in graph:
        graph[end] = [start]

for vertex in graph.keys():
    graph[vertex].sort()

print(graph)
ret = []
#Print(DFS_recursion(v, ret))
Print(DFS_stack(v))
#Print(BFS_list(v))
Print(BFS_queue(v))