[백준] 1260 DFS와 BFS

1. 문제

 

2. 아이디어

graph리스트에 정점들을 입력받아 dfs와 bfs를 적용한다.

 

3. 코드 요약

- 입력

(모두 int형)

n : 정점 개수

m : 간선 개수

v :  시작 정점 번호

 

a, b : 간선이 연결하는 두 정점 번호 (m개 줄 입력)

 

- 변수

visited : False로 (n+1) 범위

graph : [ ] (n+1) 범위 리스트

*graph 리스트에 정점과 연결되는 정점들 넣어주기

graph[a].append(b)

graph[b].append(a)

*정점 번호가 작은 것부터 방문 (정렬)

graph[i].sort()

 

- 함수

dfs 함수

: 현재 정점 visited True 후 정점 출력

현재 정점과 연결된 정점 중 visited가 False인 정점에 대해 dfs 재귀함수 호출

 

bfs 함수

: collection deque 라이브러리 필요

queue 선언

현재 정점 visited True

queue가 있으면 맨 왼쪽 원소를 popleft 후 출력

출력 정점과 연결된 정점이 False면 queue에 넣고 visited True

 

- 출력

dfs 출력 후 visited가 재사용 되기 때문에 False로 초기화 한 다음 bfs를 출력한다.

 

4. 전체 코드

from collections import deque

n,m,v=map(int,input().split())
visited=[False]*(n+1)

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


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

for i in range(len(graph)):
    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 = deque([v])
    visited[v]=True

    while queue:
        v=queue.popleft()
        print(v, end=' ')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

dfs(v)
visited=[False] * (n+1)
print()
bfs(v)