(Python) - BOJ(1260번) : DFS와 BFS

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

1260번: DFS와 BFS

---

• 해설 : 

그래프의 노드와 간선정보가 주어질 때, 1번 정점부터 BFS와 DFS로 탐색한 결과를 출력하는 문제이다.

 

 

 

---

• 풀이 :

양방향 그래프이므로 0번 노드부터 N-1번 노드까지 연결 관계를 재설정해준 후 이를 BFS와 DFS로 각각 탐색하며 현재 탐색중인 노드를 출력하도록 구현하였다.

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
input = sys.stdin.readline
 
 
def bfs(node,start):
    queue = deque([start])
    print(start,end = ' ')
 
    check = [0 for _ in range(N+1)]
    check[start] = 1
    while queue:
        x = queue.popleft()
        for i in node[x]:
            if check[i] == 0:
                print(i,end = ' ')
                queue.append(i)
                check[i] = 1
 
 
def dfs(node,start):
    visited[start] = 1
    print(start,end = ' ')
    for i in node[start]:
        if visited[i] == 0:
            dfs(node,i)
 
if __name__ == "__main__":
    N,M,V = map(int,input().split())
    nodes = [[] for _ in range(N+1)]
    visited = [0 for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        nodes[x].append(y)
        nodes[y].append(x)
    for i in range(N+1):
        nodes[i] = sorted(nodes[i])
    dfs(nodes,V)
    print('\n',end = '')
    bfs(nodes,V)