[항해]알고리즘 스터디(백준 #1260)

백준#1010

바로가기

문제 해석
DFS와 BFS로 탐색한 결과를 출력하는 프로그램을 작성한다.
단, 방문할 수 있는 정점이 여러개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.
첫 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V.
둘째 줄은 M줄인데, 간선이 연결하는 두 정점의 번호가 주어짐.

문제를 풀기 위해 알아야 할 개념들
1. BFS(너비 우선 탐색 / Breath First Search)
==너비를 우선하여 그래프를 탐색. 시작점인 루트노드와 같은 거리에 있는 노드를 우선 방문
2. DFS(깊이 우선 탐색 / Depth First Search)
==한 방향으로 갈 수 있는 만큼 깊게 탐색. 한 길로 끝까지 탐색해 리프노드를 방문하고, 이전 갈림길에서 선택하지 않았던 노드를 방문하는 식.

3. 정점
== 노드. 방문해야 할 포인트
4. 간선
== 노드 간 이어진 선
5. 인접 리스트(Adjacency list)
==각 노드에 연결된 다른 노드들을 리스트로 표현

예제 보기

코드

# Depth First Search
def dfs(n):
    print(n, end=' ')
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            dfs(i)
# Breadth First Search
def bfs(n):
    visited[n] = True
    queue = deque([n])
    while queue:
        v = queue.popleft()
        print(v, end= ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
import sys
from collections import deque
# node, branch, first node
n, m, v = map(int, sys.stdin.readline().split())
# adjacency list
graph = [[] for _ in range(n+1)]
# check list
visited = [False] * (n + 1)
# make adjacency lsit
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
# sort adjacency list
for i in range(1, n+1):
    graph[i].sort()
dfs(v)
# initialize check list
visited = [False] * (n + 1)
print()
bfs(v)