[백준 문제풀이] 1260번 : DFS와 BFS

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

1260번: DFS와 BFS

 

💡 정점번호가 작은 것부터 방문해야해서 for문을 사용한다. 1부터 시작해 확인하기 위해서.

DFS는 해당 정점에서 다시 시작하기 때문에 재귀도 사용해야 한다.

 

BFS는 재귀를 사용하지 않기 때문에 함수 안에서 visited를 초기화했다.

그리고 BFS는 queue가 empty일 때까지 사용되므로 while문을 사용해서 queue가 빌 때까지 반복한다.

 

✔ 소스코드

N,M,V=map(int,input().split())

graph=[[0]*(N+1) for i in range(N+1)]
visited=[False]*(N+1)

for i in range(M):
    a, b =  map(int, input().split())
    graph[a][b]=1
    graph[b][a]=1

def dfs(V):
    print(V,end=' ')
    visited[V]=True
    for i in range(1,N+1):
        if visited[i]==False and graph[V][i]==1:
            dfs(i)

def bfs(V):
    visited=[False]*(N+1)
    queue=[V]
    while(queue):
        visited[V]=True
        V=queue[0]
        print(V,end=' ')
        del queue[0]
        for i in range(1,N+1):
            if visited[i]==False and graph[V][i]==1:
                queue.append(i)
                visited[i]=True
dfs(V)
print()
bfs(V)