[파이썬] 백준 1260번 DFS와 BFS

문제

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

 

---

문제풀이

import sys
sys.stdin = open("input.txt", "r")

# 깊이 우선 탐색 (Depth-First Search)
# idx에는 아래 코드에서(V)를 넣어줬기 때문에 시작할 때 1이 들어간다.
def dfs(idx):
    # 함수 외부에 있는 비지티드를 가져오기 위해 글로벌 비지티드를 작성함
    global visited

    # dfs가 호출되면서 그 자리는 방문했기 때문에 트루로 변경해준다.
    visited[idx] = True

    # 현재 방문한 순서대로 출력을 해주는데 그때마다 띄어쓰기로 공백을 넣어준다
    print(idx, end=' ')
    for next in range(1, N+1): # N이 4니까 Next에 1,2,3,4가 들어간다.
        # 만약에 다음 노드가 방문된 적이 없다면 그리고 그래프에서 인덱스의 넥스트가 있다면 // 즉 넥스트가 방문된 적은 없지만 내 현재 인덱스에서 갈 수 있는 곳이라면 가겠다 -> 가서 dfs(next)
        if not visited[next] and graph[idx][next]:
            dfs(next)

# 너비 우선 탐색 (Breadth-First Search)
def bfs():
    global q, visited

    # 큐에 요소가 있을때까지 계속 반복함
    while q:
        # 큐에서 가장 위에있는 원소를 리턴하고 해당 원소 삭제 ( 0번 인덱스를 뽑아서 커에 답는다)
        cur = q.pop(0)
        visited[cur] = True
        print(cur, end=' ')
        for next in range(1, N + 1):
            if not visited[next] and graph[cur][next]:
                visited[next] = True
                q.append(next)

# 0. 입력 및 초기화
input = sys.stdin.readline
N, M, V = map(int, input().split())

# 그래프 초기화
# 2차원 배열 각 행과 열이 N + 1 by N + 1 배열
# 초기화를 0 또는 fals로 한다.
# fals만 n+1개 가지고 있는 1차원배열이고 이 1차원 배열을 n + 1 개의 행을 가지고 싶은거니까 for문을 돌려 추가해준다.
# N + 1 by N + 1가 fals로 채워져있는 2차원 배열을 만들었다
graph = [[False] * (N + 1) for _ in range(N + 1)]
# 그래프와 똑같은 1차원 배열 하나를 만들어준다.
visited = [False] * (N + 1)

# 1. 그래프 정보 입력
# n개의 간선의 정보를 그래프에 반영한다
# n번 반복하면서 a와 b의 정보를 받는다. 이때 a, b는 그래프 위치이다.
for _ in range(M):
    a, b = map(int, input().split())
    # 방문했으니까 트루로 표시 (간선은 양방향이기 때문에 a b / b a 를 둘 다 트루로 표시한다.)
    graph[a][b] = True
    graph[b][a] = True

# 2. 깊이 우선 탐색
dfs(V) # v노드부터 dfs 함수를 수행하라는 뜻
print() # 줄바꿈을 위한 프린트

# 3. 너비 우선 탐색
# 다시 폴스로 값을 바꿔준다
visited = [False] * (N + 1)
# v 값부터 시작할 수 있도록 q에 v값을 담아준다
q = [V]
# v라는 노드를 재방문하지 않도록 막음
visited[V] = True
bfs()

print(graph)

참고 강의 영상 : https://youtu.be/d3R1s_OmwAk?feature=shared