1260-백준-DFS와 BFS

1. 문제 출처

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

1260번: DFS와 BFS

2. 풀이

DFS 와 BFS 에 대한 기초적인 문제를 확인 할 수 있었다.

# 필요 라이브러리 불러오가
import copy
from collections import deque
# 입력
n, m, v = map(int, input().split())


# 그래프 값 초기화
graph = [[0 for _ in range(n)] for _ in range(n)]

# 그래피 입력 받기
# 행렬을 사용하여 그래프를 구현 하였다.
for _ in range(m):
    x,y = map(int,input().split())
    graph[x-1][y-1] = 1
    graph[y-1][x-1] = 1
    
    
def DFS():
    '''
    깊이 우선 탐색
    stack을 이용하여 구현하였다.
    '''
    dfs_result= []
    # 스텍에 시작값을 넣는다
    stack = [v-1]
    # 방문 여부 리스트
    visted = [False] * n
    # stack 이 빌때까지 반복
    while stack:
        node = stack.pop()
        if visted[node]:
            continue
        visted[node] = True
        dfs_result.append(node+1)
        # 문제는 노드 숫자가 작은 순으로 방문 했으므로 
        # 다음과 같이 역순으로 range를 돌린다.
        for idx in range(n-1,-1,-1):
            if graph[node][idx] == 1 and visted[idx] == False:
                stack.append(idx)
    for i in dfs_result:
        print(i,end = " ")
    print()
    

def BFS():
    '''
    너비 우선 탐색
    queue를 이용하여 구현하였다.
    '''
    bfs_result = []
    queue = deque([v-1])
    visted = [False] * n
    while queue:
        node = queue.popleft()
        if visted[node]:
            continue
        visted[node] = True
        bfs_result.append(node+1)
        for idx in range(n):
            if graph[node][idx] == 1 and visted[idx] == False:
                queue.append(idx)
    for i in bfs_result:
        print(i,end = " ")
        
                
DFS()
BFS()