[백준] 1260 - DFS와 BFS (Python)

문제

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

문제 설명

문제 이름 그대로 DFS와 BFS를 구현하라는 문제..ㅎ

제출 코드

import sys

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

    for node in range(1, N+1):
        if visited[node] is False and matrix[v][node] == 1:
            dfs(node)

def bfs(v):
    queue = [v]
    visited[v] = True

    while queue:
        pop_v = queue.pop(0)
        print(pop_v, end=' ')
        for node in range(1, N+1):
            if visited[node] is False and matrix[pop_v][node] == 1:
                queue.append(node)
                visited[node] = True

N, M, V = map(int, sys.stdin.readline().strip().split())
matrix = [[0]*(N+1) for i in range(N+1)]

for i in range(M):
    n1, n2 = map(int, sys.stdin.readline().strip().split())
    matrix[n1][n2] = matrix[n2][n1] = 1

visited = [False for _ in range(N + 1)]
dfs(V)
print()
visited = [False for _ in range(N + 1)]
bfs(V)

결과

---

정리

개념

• DFS (Depth-First Search, 깊이 우선 탐색)
  : 루트를 시작으로 탐색을 한다면 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳까지 내려간다. 더 이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 곳이 있으면 즉각 내려간다.
  "현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색"

• BFS (Breadth-First Search, 너비 우선 탐색)
  : 루트를 시작으로 탐색을 한다면 먼저 루트의 자식을 차례로 방문한다. 다음으로는 루트 자식의 자식, 즉 루트에서 두개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다.
  "현재 정점에 연결된 가까운 점들부터 탐색"

• 문제 유형 특징
  1) 그래프의 모든 정점을 방문하는 것이 중요한 문제
  -> DFS, BFS 모두 가능
  2) 경로의 특징을 저장해두어야 하는 문제
  -> DFS (!BFS는 경로의 특징을 가지지 못함!)
  3) 최단거리를 구해야 하는 문제
  -> BFS (현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색할때 먼저 찾아지는 경로가 답)

• 구현 방법
  DFS: 스택 또는 재귀함수를 이용하여 구현
  BFS: 큐를 이용하여 구현

주석있는 코드

# DFS와 BFS
import sys

# Depth-First Search (깊이 우선 탐색)
# 자기 자신을 호출하는 순환 알고리즘
def dfs(v):
    # 시작 정점 방문 여부를 true로 변경
    visited[v] = True

    print(v, end=' ')

    # 재귀 함수 선언
    for node in range(1, N+1):
        if visited[node] is False and matrix[v][node] == 1:
            dfs(node)


# Breadth-First Search (너비 우선 탐색)
# 루트노트에서 시작해서 인접한 노드 먼저 탐색
# FIFO 큐사용
def bfs(v):
    # 큐에 start node를 넣음
    queue = [v]
    visited[v] = True

    while queue:
        # 큐에서 맨 앞의 노드를 dequeue (0번 인덱스 pop)
        pop_v = queue.pop(0)
        print(pop_v, end=' ')
        for node in range(1, N+1):
            if visited[node] is False and matrix[pop_v][node] == 1:
                queue.append(node)
                visited[node] = True


# 입력받기
N, M, V = map(int, sys.stdin.readline().strip().split())
matrix = [[0]*(N+1) for i in range(N+1)]
#print(list)

for i in range(M):
    n1, n2 = map(int, sys.stdin.readline().strip().split())
    matrix[n1][n2] = matrix[n2][n1] = 1

# 방문 여부 확인해야 함
visited = [False for _ in range(N + 1)]
dfs(V)
print()
# 방문 여부 다시 초기화
visited = [False for _ in range(N + 1)]
bfs(V)

느낀점

이 문제같은 경우는 노골적으로(?) DFS와 BFS를 구하라는 문제였지만 사실 나에게 필요한 역량은 응용 문제를 보고 'DFS를 사용하는 문제다!' 또는 'BFS를 사용하는 문제다!'라고 생각하고 적용하는 것이다!! 코딩테스트에 많이 나온다고 하니까 잘 알아두어야겠다..ㅎ