1260. DFS와 BFS

문제 링크

1260. DFS와 BFS

문제 코드

from collections import deque

node, edge, start = list(map(int,input().split()))

dfs_visited =[0]*node
bfs_visited = [0]*node

graph = [[0 for col in range(node)]for row in range(node)]

for i in range(edge):
    x,y = list(map(int,input().split()))
    graph[x-1][y-1] = 1
    graph[y-1][x-1] = 1

dfs_result = str(start)+" "

dfs_visited[start-1] = 1

def back_tracking(tmp):
    global node,dfs_result
    for i in range(node):
        if graph[tmp][i] == 1 and dfs_visited[i] == 0:
            dfs_visited[i] = 1
            dfs_result += str(i+1) +" "
            back_tracking(i)

back_tracking(start-1)

bfs_result = str(start)+" "
bfs_que = deque()
bfs_que.append(start-1)
bfs_visited[start-1] =1
while len(bfs_que)>0:
    tmp = bfs_que.popleft()
    for i in range(node):
        if graph[tmp][i] == 1 and bfs_visited[i] ==0:
            bfs_visited[i] = 1
            bfs_result += str(i+1)+" "
            bfs_que.append(i)

print(dfs_result)

print(bfs_result)

문제 풀이

• DFS와 BFS를 구현해서 푸는 간단한 문제
• DFS를 큐를 이용해 보려했으나 꼬임
• DFS는 백트래킹으로 하자