[백준] 1260 - DFS와 BFS

문제

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

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하라. 단, 방문할 수 있는 정점이 여럿인 경우에는 정점 번호가 작은 것부터 방문한다.

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

 

 

접근

2024.05.08-[알고리즘] 너비 우선 탐색(BFS) 이란, 2024.05.12-[알고리즘] 깊이 우선 탐색(DFS) 이란에서 살펴본 대로 구현하면 된다.

 

 

구현

1. 입력값 초기화

import sys

N, M, V = map(int, sys.stdin.readline().split())

 

2. 그래프 초기화

값을 입력받아 그래프를 초기화한다. 값이 적은 정점부터 방문할 수 있도록 입력을 완료한 뒤에는 각 정점에서 방문할 수 있는 정점 목록을 정렬한다.

graph = {i: [] for i in range(1, N + 1)}

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, N + 1):
    graph[i].sort()

 

3. DFS 구현

그래프와 시작 정점을 입력받아 정점의 방문 여부를 반환하는 DFS 함수를 구현한다. 단, 정점의 방문 순서를 따질 수 있도록 visited에 방문 여부를 나타내는 부울값과 방문 순서를 나타내는 정수값의 튜플로 visited 딕셔너리를 구성한다.

def dfs(graph, start=1):
    visited = {k: (False, -1) for k in graph.keys()}
    stack = [start]
    i = 0

    while stack:
        cur = stack.pop()

        if not visited[cur][0]:
            i += 1
            visited[cur] = (True, i)
            stack.extend(graph[cur][::-1])

    return visited

그리고 방문 처리하면서 방문 순서도 함께 처리할 수 있도록 한다.

 

4. BFS 구현

DFS와 동일하게 그래프와 시작 정점을 입력받아 정점의 방문 여부를 반환하는 BFS 함수를 구현한다. BFS도 방문 순서를 처리할 수 있도록 구현한다.

def bfs(graph, start=1):
    visited = {k: (False, -1) for k in graph.keys()}
    queue = [start]
    i = 0
    visited[start] = (True, i)

    while queue:
        cur = queue.pop(0)

        for nxt in graph[cur]:
            if not visited[nxt][0]:
                i += 1
                queue.append(nxt)
                visited[nxt] = (True, i)
    return visited

 

5. 결과 출력

방문한 정점만 순서대로 출력할 수 있도록 방문 여부가 True인 정점만 필터링한 후 방문 순서대로 정렬하여 출력한다.

result_dfs = sorted([(k, v[1]) for k, v in dfs(graph, start=V).items() if v[0]], key=lambda x: x[1])
result_bfs = sorted([(k, v[1]) for k, v in bfs(graph, start=V).items() if v[0]], key=lambda x: x[1])

print(*[i[0] for i in result_dfs])
print(*[i[0] for i in result_bfs])

 

 

참고 문서

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