230219 [1260: DFS&BFS]

True → 1, False → 0 로 구현

 

import sys
from collections import deque

input = sys.stdin.readline

# N : 정점개수, M : 간선개수, V : 탐색시작점
N, M, V = map(int, input().rstrip().split())

# 인접행렬을 모두 0으로 구성
matrix = [[0]*(N+1) for i in range(N+1)]

#방문할 곳 체크 리스트 정점 갯수만큼 크기 구성
visited_dfs = [0]*(N+1)
visited_bfs = [0]*(N+1)

# 간선 갯수 만큼 입력받기, 입력받는 값에 대해 영행렬에 1 삽입 -> 인접리스트 생성
for i in range(M):
    n1, n2 = map(int, input().rstrip().split())
    matrix[n1][n2] = matrix[n2][n1] = 1

def DFS(V):
    visited_dfs[V] = 1 # V값 방문처리
    print(V, end= ' ')

    for i in range(1, N+1):
				# i값을 방문하지 않고 V와 연결이 되어잇다면
        if(visited_dfs[i] == 0 and matrix[V][i] == 1):
						# 해당 i값으로 깊이 탐색
            DFS(i)

def BFS(V):
    visited_bfs[V] = 1 # V값 방문처리
    queue = deque([V])

    while queue: #q가 빌 때까지
        V = queue.popleft() # 큐에 있는 첫번째 값 꺼내기
        print(V, end = ' ')

        for i in range(1, N+1): #1부터 N까지 돔
						# 만약 i값을 방문하지 않았고, V와 연결이 되어있다면
						# 그 i값 추가 & 방문처리
            if(visited_bfs[i] == 0 and matrix[V][i] == 1):
                queue.append(i)
                visited_bfs[i] = 1

DFS(V)
print()
BFS(V)