[BOJ] 1260 DFS와 BFS (Pytyon3)

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1  
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1  
1 2 4 3
1 2 3 4


예제 입력 2  
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 2  
3 1 2 5 4
3 1 4 2 5

풀이

좌우좌표계로 연결된 노드로 생각하고 bfs를 사용하여 방문한적이 없다면 점프하기 전의 위치에서 1을 더한값을 현재위치에 저장해 주며 앞으로 끝까지 나아간다. 그 이후에 주미가 있는 곳의 숫자를 출력해주면, 그 숫자가 동규가 주미에게 도달하기위한 최소 이동 횟수가 된다.

코드

from collections import deque

n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    dotA, dotB = map(int, input().split())
    graph[dotA].append(dotB)
    graph[dotB].append(dotA)
    
def dfs(graph, v, visited):
    # 현재 노드를 방문처리
    visited[v] = True
    print(v, end = ' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
   
def bfs(graph, start, visited):
    queue = deque([start])
    
    visited[start] = True
    
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
for i in range(1, n+1):
    graph[i].sort()               


dfs(graph, v, visited)
visited = [False] * (n+1)
print()
bfs(graph, v, visited)

5 5 3
5 4
5 2
1 2
3 4
3 1
3 1 2 5 4 
3 1 4 2 5 

문제풀이

깊이,너비우선 탐색의 기초를 구현해보는 문제였다.

dfs랑 bfs는 복잡해서 그런가 기억이 진짜 너무 안난다…

먼저 dfs는 깊이 우선 탐색으로, 인접노드를 계속 타고 들어가 방문하지 않은 인접노드가 있을때까지 탐색한뒤, 다시 돌아와 반복하며 모든 노드를 탐색하는 방식이고,

bfs는 너비 우선 탐색으로 먼저 주변 노드들을 모두 탐색한 뒤에 다음 depth로 이동해서 탐색하는 방식으로, 인접 노드를 먼저 모두 방문하고 다음 depth로 이동하는 방식이다.

dfs의 경우는 재귀함수를 이용해서, 노드를 방문하면 시작 노드와 인접한 노드를 계속 타고 들어가 재귀 함수가 종료된 후 다음 방문하지 않은 시작노드의 인접노드를 방문하여 동일하게 진행한다.

bfs는 큐를 하나 만든 뒤, 시작노드의 인접노드를 방문하며 순서대로 큐에 넣어 시작노드와 가까운 인접노드를 우선적으로 방문하며 차례대로 다음 depth를 방문하여 진행한다.