[백준 / python] 1260번 DFS 와 BFS

bfs와 dfs를 모두 함수로 구현해서 각각 한번씩 실행을 해줘야 한다.

각각 한 번씩만 하면 되므로 이를 기록할 리스트를 1개씩 만들어두고 입력받은 점에 대해서는 2차원 배열에 저장해두자

bfs와 dfs를 실행하면서 각각의 경우에 2차원 배열에 저장된 경로들을 참고하여 출력할 수 있는 경우들을 출력하고 출력 형식은 한 줄로 붙어있어야 하므로 그때그때 출력하고 end=" "를 통해서 한 줄로 출력하자.

 

 

import sys
from collections import deque

def main():
    N, M, V = map(int, sys.stdin.readline().split())
    graph = [[False] * (N+1) for _ in range(N+1)]

    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        graph[a][b] = True
        graph[b][a] = True

    visited1 = [False] * (N+1)
    visited2 = [False] * (N+1)

    def bfs(V):
        q = deque([V])
        visited2[V] = True
        while q:
            V = q.popleft()
            print(V, end=" ")
            for i in range(1, N + 1):
                if not visited2[i] and graph[V][i]:
                    q.append(i)
                    visited2[i] = True

    def dfs(V):
        visited1[V] = True
        print(V,end=" ")
        for i in range(1, N+1):
            if not visited1[i] and graph[V][i]:
                dfs(i)

    dfs(V)
    print()
    bfs(V)

    return

if __name__ == "__main__":
    main()