[알고리즘] 백준 1260 : DFS와 BFS - S2

2023.04.06 풀이

import sys
input=sys.stdin.readline
from collections import deque

n,m,v=map(int, input().split())
arr=[[]*(n+1) for _ in range(n+1)]

visited_bfs=[False]*(n+1)
visited_dfs=[False]*(n+1)

def dfs(v):
    visited_dfs[v]=True
    print(v, end=" ")
    for i in sorted(arr[v]):
        if visited_dfs[i]==False:
            dfs(i)

def bfs(v):
    visited_bfs[v]=True
    queue=deque([v])
    while queue:
        k=queue.popleft()
        print(k, end=" ")
        for i in sorted(arr[k]):
            if visited_bfs[i]==False:
                visited_bfs[i]=True
                queue.append(i)

for i in range(m):
    a, b=map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

dfs(v)
print()
bfs(v)

다른 풀이

import sys
input = sys.stdin.readline

n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

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

for i in range(n+1):
    graph[i].sort()


def dfs(v):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(i)


def bfs(v):
    queue = [v]
    visited[v] = False
    while queue:
        v = queue.pop(0)
        print(v, end=' ')
        for i in graph[v]:
            if visited[i]:
                queue.append(i)
                visited[i] = False


dfs(v)
print()
bfs(v)

check point

DFS : 스택구조 이용

• 현재노드 방문처리 (탐색 시작 노드를 스택에 삽입)
• 인접노드 중에 크기 순으로
  • 방문하지않은 노드가 있으면
    - 재귀

BFS : 큐 구조 이용

• 큐 라이브러리 사용 (시작노드 넣기)
• 현재노드 방문처리
• 큐가 빌 때 까지 반복
  • 큐에서 하나의 원소 뽑고
  • 출력
  • 해당 원소와 연결된 원소중 크기 순으로
    - 아직 방문하지 않은 원소를
    • 큐에 삽입
    • 방문처리