[Python] 1260번 : DFS와 BFS

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

1260번: DFS와 BFS

 

문제 3줄 요약

1. 그래프를 DFS와 BFS로 탐색한 결과를 출력한다.

2. 여러 정점을 방문할 수 있는 경우, 작은 번호부터 방문

3. 정점 번호는 1번부터 N번까지이다.

 

---

알고리즘하면 빠질 수 없는

DFS(깊이 우선 탐색),

BFS(너비 우선 탐색) 구현문제다!

 

 

간단하게

DFS와 BFS의 차이를 본다면,

 

 

DFS의 경우, 부모 노드 이후에

(2) 자식 노드의 (4) 자식, (2) 자식 노드의 (4) 자식노드의 자식이 없다면,

(2) 자식 노드의 (5) 같은 깊이의 형제 노드순으로

왼쪽 트리를 먼저 탐색한 후, 오른쪽 트리를 넘어가는 방식으로 탐색합니다.

 

BFS의 경우, 부모 노드 이후

(2), (3) 자식 노드 탐색,

(2), (3) 자식 노드의 (4), (5), (6), (7) 자식 노드 탐색을 하게 됩니다.

DFS와 마찬가지로

왼쪽 트리의 자식 노드를 먼저 탐색하지만,

깊이가 같은 형제 노드를 모두 탐색하고

그 자식인 노드를 탐색하러 깊이를 한 단계 내려간다는 점!

 

따라서

DFS는 주로 스택,

BFS는 큐 자료구조를 이용하여 구현한다.

 

---

 

STEP 1)

정점 사이의 간선 정보를 리스트를 이용하여 구현해준다.

 

Input 이 1 2 라고 주어진다면,

1과 2사이의 간선이 있다는 뜻이다.

 

이는 문제의 간선이 양방향이기 때문에

즉, 2 1 도 동시에 만족한다는 뜻이 된다.

 

따라서 아래와 같이

각 정점 별 연결되어 있는 간선을 추가해준다.

아래 코드에선 defaultdict를 set로 만들어줬는데,

리스트를 사용하여 만들어주어도 상관이 없을 것 같다.

 

중복이 없을텐데,,

나 왜 set 썼지..?

 

여튼 코드를 보자!

 

from sys import stdin
# 간선 정보를 담을 딕셔너리
from collections import defaultdict
from collections import deque

N, M, V = map(int,stdin.readline().split())
# v_dict : 정점의 간선을 담는 딕셔너리
# visited : DFS와 BFS에서 방문 판정해줄 리스트
v_dict, visited = defaultdict(set), [1]*(N+1)

for _ in range(M):
    start, move = map(int,stdin.readline().split())
    
    # 간선 정보 담기
    v_dict[start].add(move)
    v_dict[move].add(start)

---

 

STEP 2)

반복문 + 자료구조, 방문 확인으로

DFS, BFS 구현 

 

visited 리스트를 이용하여 중복 방문을 방지하고,

DFS는 후입선출 스택 구조를 위해 리스트를 사용

 

Ex)

stack = [3, 2]

(2) pop → (4), (5) push

stack = [3, 5, 4]

 

BFS는 선입선출 큐 구조를 위해 deque를 사용

 

Ex)

deque = [1]

(1) popleft → (2), (3) push

deque = [2, 3]

 

간단히 생각하면,

stack은 값들이 오른쪽부터 빠져나가는 구조로,

deque는 값들이 왼쪽부터 빠져나가는 구조로

DFS와 BFS를 구현한 것이다.

 

코드를 통해 살펴보자!

 

from sys import stdin
from collections import defaultdict
from collections import deque

def dfs(v):
    # dfs_list : dfs에 사용할 자료구조
    # answer_list : 정답 원소 넣을 리스트
    # visited[v] : 방문 판정 리스트
    dfs_list, answer_list, visited[v] = [],[v], 0

    # 이어진 간선 내림차순으로 정렬해서 넣기
    # -> 작은 정점부터 방문해야하기 때문에 리스트에 역순으로 넣는 것!
    for target in sorted(list(v_dict[v]), reverse=True):
        dfs_list.append(target)
    
    while(len(dfs_list) > 0):
        next = dfs_list.pop()
        
        # 방문 원소인지 체크
        if visited[next]:
            visited[next] = 0
            answer_list.append(next)

            # 연결된 간선이 방문하지 않은 원소라면, 리스트에 추가
            # 이것 또한 역순으로 넣기
            for target in sorted(list(v_dict[next]), reverse=True):
                if visited[target]:
                    dfs_list.append(target)
    
    print(*answer_list)

def bfs(v):
    # bfs_deque : bfs에 사용할 자료구조
    bfs_deque, answer_list, visited[v] = deque(),[v], 0

    # 이어진 간선 내림차순으로 정렬해서 넣기
    # -> 선입선출 구조이기 때문에 역순x
    for target in sorted(list(v_dict[v])):
        bfs_deque.append(target)
    
    while(len(bfs_deque) > 0):
        next = bfs_deque.popleft()
        
        # 방문 원소인지 체크
        if visited[next]:
            visited[next] = 0
            answer_list.append(next)

            # 연결된 간선이 방문하지 않은 원소라면, 리스트에 추가
            for target in sorted(list(v_dict[next])):
                if visited[target]:
                    visited[target] = 1
                    bfs_deque.append(target)
    
    print(*answer_list)

N, M, V = map(int,stdin.readline().split())
v_dict, visited = defaultdict(set), [1]*(N+1)

for _ in range(M):
    start, move = map(int,stdin.readline().split())
    
    v_dict[start].add(move)
    v_dict[move].add(start)

dfs(V)
visited = [1]*(N+1)
bfs(V)

---

처음에는 낯설고 어려웠지만

DFS와 BFS는 접해볼 문제들이 많기도하고

코딩테스트에 자주 나오던 문제라 이제는 조금은 익숙해졌다.

 

중요한 알고리즘이니

여러번 보자!

 

끝