백준1260 - DFS와 BFS

주어진 경로에 대해 dfs, bfs로 순회한 결과를 출력하는 문제이다.

 

1. dfs, bfs의 개념을 알고 있는가?

2. 그래프를 어떻게 표현할 것인가?

3. 주어진 그래프 순회 법에서 dfs와 bfs를 어떻게 적용할 것인가?

 

위 세가지를 알아야 문제를 해결할 수 있다. 

 

from collections import deque


def dfs(graph, begin, visited_list):
    b = begin - 1
    visited_list.append(b)
    print(begin, end=' ')

    for i, v in enumerate(graph[b]):
        if v == 1 and i not in visited_list:
            visited_list.append(i)
            dfs(graph, i + 1, visited_list)

    return 0

def bfs(graph, begin, visited_list):
    b = begin - 1
    q = deque()

    q.append(b)
    visited_list.append(b)
    print(begin, end=' ')

    while True:
        if len(q) == 0:
            break
        for i, v in enumerate(graph[q[0]]):
            if v == 1 and i not in visited_list:
                q.append(i)
                visited_list.append(i)
                print(i + 1, end=' ')
        q.popleft()

    return 0


int_v, int_e, begin = map(int, input().split())

graph = [[0] * int_v for i in range(int_v)]

for i in range(int_e):
    x, y = map(int, input().split())
    graph[x - 1][y - 1] = 1
    graph[y - 1][x - 1] = 1

dfs(graph, begin, [])
print()
bfs(graph, begin, [])

• 파이썬 풀이