[백준] 1260번 DFS와 BFS, 파이썬 문제 풀이

문제

백준 1260번 DFS와 BFS를 구현하는 문제를 해결했습니다.

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

1260번: DFS와 BFS

문제

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

입력

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

출력

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

 

▲ 예시

 

문제 풀이

전에 풀었던 2606번 바이러스 문제에서 DFS와 BFS를 활용해서 문제를 해결했었습니다.

참고 - [백준] 2606번 바이러스, 파이썬 문제 풀이, DFS와 BFS 차이

이번 문제는 다른 내용 없이 노드와 간선, 시작 노드가 주어지면 DFS, BFS를 활용해 탐색하는 것입니다. 여러 개의 간선이 연결되어 있을 경우 노드 번호가 작은 것부터 탐색하게 됩니다. 

 

2차원 리스트에 노드와 간선의 정보를 저장합니다. 노드 번호에 맞는 인덱스에 연결된 간선의 정보를 저장합니다. 여러 개의 간선이 있을 경우, 작은 것부터 탐색해야하므로 각각에 대해서 오름차순으로 정렬합니다. 

 

먼저, DFS는 재귀 호출을 통해 구현할 수 있습니다. 방문하지 않은 노드가 있으면 방문하게 됩니다. DFS는 다음 노드를 방문하고, 그 다음 노드가 있으면 계속해서 방문하고 돌아오면서 방문하지 않은 노드를 방문하는 순서대로 탐색하는 알고리즘입니다. 그렇기 때문에 재귀 호출로 쭉쭉 들어갈 수 있는 것입니다.

 

BFS는 큐와 반복문을 통해 구현할 수 있습니다. 현재 노드와 연결되어 있는 노드를 우선으로 방문하고, 그 다음 노드로 이동해 방문하는 것입니다. 그렇기 때문에 반복문을 통해 현재 노드와 연결되어 있는 곳을 먼저 방문하고 넘어가는 것입니다. 이 때, 방문해야 하는 곳을 큐에 저장하고, 큐에서 빼면서(Dequeue) 그 노드를 방문하는 것입니다.

 

코드로 확인하면 다음과 같습니다.

def DFS(v):
    visited[v]=1
    dfs.append(v)
    for i in node[v]:
        if (visited[i]==0):
            DFS(i)

def BFS(v):
    visited[v]=1
    bfs.append(v)
    queue = [v]

    while(queue):
        for i in node[queue.pop(0)]:
            if(visited[i]==0):
                visited[i]=1
                bfs.append(i)
                queue.append(i)
##################MAIN##################
N, M, V = map(int, input().split())

node =[[]for _ in range(N+1)]
visited = [0]*(N+1)
dfs = []
bfs = []

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

for j in range(N+1):
    node[j].sort()

DFS(V)
for j in range(N+1):
    visited[j]=0
BFS(V)

for m in dfs:
    print(m, end=' ')
print()
for n in bfs:
    print(n, end=' ')

정리

문제를 제출하고 오답이 나왔는데, 각각의 탐색 결과를 리스트에 저장하고 리스트 형태로 출력해서 오답이 나왔습니다. 출력 형태를 확인하고 제출하는 습관이 필요할 것 같습니다.