[Python] 백준 온라인 저지 1260번 - DFS와 BFS

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

1260번: DFS와 BFS

 

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 

정점 번호는 1번부터 N번까지이다.

 

 

 

 

[Python]

 

풀이 방법:

 

• DFS(깊이 우선 탐색)의 경우 최상위 노드부터 시작하여 하위노드까지 하나의 방향으로 깊게 탐색한 뒤, 다시 올라가서 다른 노드를 동일한 방법대로 깊게 탐색한다
• DFS 문제의 경우 스택과 재귀를 이용하여 문제를 풀 수 있다

 

• BFS(너비우선탐색)의 경우에는 최상위 노드부터 시작하여 다음노드를 모두 탐색하고, 그 다음 노드를 모두 탐색한다
• BFS의 경우 큐를 이용하여 풀면 되기에 deque 모듈을 사용하여 풀면 좋다.

 

코드:

# 입력 변수 받기
N, M, V = map(int, input().split())

# 인접 영행렬 생성
matrix=[[0] * (N + 1) for i in range(N + 1)]

# 방문한 곳 체크를 위한 배열 선언
visited = [0] * (N + 1)

# 입력 받는 두 값에 대해 영행렬에 1 삽입
for i in range(M):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1


def dfs(V):
    # 방문한 곳은 1 넣기
    visited[V] = 1
    
    print(V, end=' ')
    
    # 재귀 함수 선언(V와 인접한 곳을 찾고 방문하지 않았다면 함수 실행)
    for i in range(1,N+1):
        if(visited[i]==0 and matrix[V][i]==1):
            dfs(i)

            
def bfs(V):
    # 방문해야 할 곳을 순서대로 넣을 큐
    queue = [V]
    
    # dfs 를 완료한 visited 배열(1로 되어있음)에서 0으로 방문체크
    visited[V] = 0
    
    # 큐 안에 데이터가 없을 때 까지
    while queue:
        V = queue.pop(0)
        print(V, end=' ')
        for i in range(1, N + 1):
            if(visited[i] == 1 and matrix[V][i] == 1):
                queue.append(i)
                visited[i] = 0

dfs(V)
print()
bfs(V)