백준 1260

- 그래프는 인접행렬 방식으로 모두 0으로 초기화한뒤 연결된 노드들 사이의 관계만 1로 변경

- dfs의 경우 최상단노드부터 시작해서 인접 노드1 -> 인접노드1과 인접한 노드 순으로 계속 방문하며 노드 번호 출력하고, 인접한 노드가 더이상 없다면 한단계 상단노드로 가서 해당 과정을 반복

- bfs의 경우는 최상단노드부터 시작해서 인접노드를 큐에 넣고 pop하며서 먼저 큐에 들어간 노드들부터 탐색함

 

# 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호 입력받기
n, m, v = map(int, input().split())

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

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

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

    for i in range(1, n+1):
        if (visited[i]==False and graph[v][i] ==1): # 인접한 노드가 있고, 방문하지 않았었다면
            dfs(i) # 재귀호출

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

    while queue:
        v = queue.pop(0) # 먼저 탐색하기 시작한거 주변을 먼저 탐색하기 위해서 ( 너비 우선 탐색)
        print(v, end= ' ')
        for i in range(1, n+1):
            if (visited[i]==True and graph[v][i] ==1): # 인접한 노드가 있고, 방문하지 않았었다면
                queue.append(i)
                visited[i] = False

dfs(v)
print()
bfs(v)