백준 1260 : DFS와 BFS (파이썬)

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

1260번: DFS와 BFS

 백준 온라인 저지 사이트에는 다양한 문제집이 있다.

그 중에서도 삼성 SW 역량테스트에 대비하여 DFS, BFS 필수 문제들을 따로 정리해둔 문제가 있었다.

이번 문제는 DFS, BFS에 관해 기본적이지만 아주 핵심 내용을 담고 있는 문제를 간단하게 풀어보았다.

문제는 아주 간단하다. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하면 된다.

 

1. 연결관계 그래프로 표현하기

 예제 1을 보면 서로 어떤 노드들끼리 연결되어있는지 알려준다. 해당 값들을 그냥 사용할 수 없고, 그 관계들을 이용하여 그래프를 구성해주어야 한다.

 

1	2
1	3
1	4
2	4
3	4

위와 같이 노드간의 연결관계는 그래프로 표현하면 다음과 같이 된다.

 

그렇다면 그래프를 리스트로 표현하면, graph = [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]] 이런식으로 구성이된다. 따라서, 정보들을 탐색할 때 각 노드에 연결 되어있는지 체크를 전부 해주고 리스트에 추가하면 된다. 이 때, 관행적으로 낮은 수부터 지정하게 되므로, sort함수를 사용하여 오름차순으로 만들어주고 저장하면 끝.

# 간선 연결관계 구축
graph = [[]]
for j in range(1, n + 1) :
    temp = []
    for i in range(len(info)):
        if j == info[i][0] :
            temp.append(info[i][1])
        elif j == info[i][1] :
            temp.append(info[i][0])
    temp.sort()
    graph.append(temp)

2. DFS & BFS

 DFS와 BFS의 차이는 데이터가 들어오고 나갈 때 후출 or 선출을 따진다.

DFS는 선입 후출의 구조이다. 스택에 데이터가 쌓이고 나갈 때는 가장 나중에 들어온 데이터가 먼저 나가게 된다. 이와 반대로 BFS 는 먼저 들어간 데이터를 먼저 꺼내는 방식이다. DFS에서는 주로 재귀함수를 이용하여 구현하고, BFS는 queue를 이용하여 필요한 데이터들을 조사하게 된다. 위의 예제를 활용해서 각 탐색 알고리즘이 데이터를 조사하는 순서를 표현해보면 다음과 같다.

BFS 과정을 더 알아보기 쉽게 표현하면, 1번 노드 에 큐를 삽입하고 방문처리 한후, 인접 노드 2, 3, 4 를 전부 넣고 넣은 순서대로 다시 '선출'하면서 인접노드를 조사하는 방식이다.

3. 전체 코드

 deque를 이용하여 queue를 구현할 수 있으나, 최대한 패키지를 배제하기 위하여 사용하지 않고 파이썬 기본 함수들을 이용하였다.

n, m, v = map(int, input().split())
# 간선이 연결하는 두 정점의 번호가 주어짐
info = [list(map(int, input().split())) for _ in range(m)]
# 간선 연결관계 구축
graph = [[]]
for j in range(1, n + 1) :
    temp = []
    for i in range(len(info)):
        if j == info[i][0] :
            temp.append(info[i][1])
        elif j == info[i][1] :
            temp.append(info[i][0])
    temp.sort()
    graph.append(temp)
    
visited_d = [False] * len(graph)
visited_b = [False] * len(graph)
dfs_list , bfs_list = [], []
def dfs(g, x, visited) :
    # 방문 처리
    dfs_list.append(str(x))
    try :
        visited[x] = True
    except :
        print('error', x)
    # print(x, end = ' ')
    # 깊이 우선 탐색
    for i in g[x] :
        if not visited[i] :
            dfs(g, i, visited)

def bfs(g, x, visited) :
    q = [x]
    visited[x] = True
    while q :
        v = q[0]
        del q[0]
        bfs_list.append(str(v))
        # print(v, end = ' ')
        for i in g[v] :
            if not visited[i] :
                visited[i] = True
                q.append(i)

dfs(graph, v, visited_d)
bfs(graph, v, visited_b)
print(' '.join(dfs_list))
print(' '.join(bfs_list))