#1260 DFS와 BFS [백준](H99.32)

📄문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

예제 입력1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력1

1 2 4 3
1 2 3 4

🖋️코드1

import sys

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

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

for _ in range(m):
    adj = list(map(int, input().split()))
    graph[adj[0]][adj[1]] = 1
    graph[adj[1]][adj[0]] = 1

def dfs(v):
    visited[v] = True
    print(v, end=" ")				  # 한줄씩 안나오고 한줄에 다나오게 하기
    for i in range(1, n+1):
        if not visited[i] and graph[v][i] == 1:   # if not은 visited[i]가 False였을때
            dfs(i)

def bfs(v):
    visited[v] = False         # dfs에서 체크 할때 True로 바꿔줘서 이제는 False로 체크
    queue = [v]                # v를 스택형식으로 넣어주고
    while queue:
        v = queue.pop(0)       # 이때까지 돌아본 노드들을 앞에서부터 빼준다
        print(v, end=" ")      # 그리고 하나씩 프린트 해주고
        for i in range(1, n+1): 
            if visited[i] and graph[v][i] == 1:     # 방문하지 않았고, 시작노드랑 연결되어 있는 모든 노드부터 방문  
                queue.append(i)
                visited[i] = False  

dfs(v)
print()         # end =" " 때문에 계속 한줄로 나오니 중간에 <p>하나 넣어주는식
bfs(v)

adj = [[0, 0, 0, 0, 0],
       [0, 0, 1, 1, 1],
       [0, 1, 0, 0, 1],    #그래프는 나타내면 요런식이다 앞에 [0]들은 인덱스를 안헷갈리기 위함이라 안쓴다.
       [0, 1, 0, 0, 1],
       [0, 1, 1, 1, 0]]