[BOJ][Python] 1260 DFS와 BFS

[문제]

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

[코드]

#S2_1260 DFS와 BFS.py

from collections import deque

#dfs
def dfs(x):						#깊이우선탐색
    global graph, visit, answer
    visit[x] = 1					#현재 노드 방문 표시 
    answer.append(x)					#방문한 노드 answer 추가 
    
    for i in range(1, n+1):
        if graph[x][i] == 1 and not visit[i]:	
            dfs(i)					#재귀 호출로 깊이 탐색 

    return answer

#bfs
def bfs(start):						#너비우선탐색
    global graph, visit, answer
    queue = deque([start])				#deque로 설정
    visit[start] = 1					#시작 노드 방문 표시 

    while queue:					#queue가 빌 때까지 반복 실행
        x = queue.popleft()				#큐에서 노드를 꺼내 방문 여부를 체크하고 
        answer.append(x)				#결과 리스트에 추가

        for i in range(1,n+1):
            if graph[x][i] == 1 and not visit[i]:	#방문하지 않은 노드를 큐에 넣고
                queue.append(i)				#방문 여부를 체크
                visit[i] = 1

    return answer

#main
n, m, v = map(int,input().split())			#노드 수, 간선 수, 시작 노드 

graph = [[0] * (n+1) for _ in range(n+1)]		#그래프 배열 생성
visit = [0] * (n+1)					#방문 노드 표시할 배열 생성			
answer = []						#방문 순서를 출력할 배열 생성

for i in range(m):
    v1, v2 = map(int,input().split())
    graph[v1][v2] = 1					#문제에서 양방향 그래프라고 명시 
    graph[v2][v1] = 1		

dfs(v)
print(' '.join(map(str,answer)))

visit = [0] * (n+1)					#같은 변수명을 쓰므로 초기화 필요 
answer = []		

bfs(v)
print(' '.join(map(str,answer)))