[boj] DFS와 BFS_1260

from collections import deque

# dfs 함수
def dfs(par_graph, par_v, par_visited):
    visited[par_v] = True
    result_dfs.append(par_v)
    for i in par_graph[par_v]:
        if not visited[i]:
            dfs(par_graph, i, par_visited)

#bfs 함수
def bfs(par_graph, par_v, par_visited):
    visited[par_v] = True
    queue.append(par_v)
    while queue:
        v = queue.popleft()
        result_bfs.append(v)
        for i in par_graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

queue = deque()

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

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

for _ in range(m):
    temp_list = list(map(int, input().split()))
    temp_num1 = temp_list[0]
    temp_num2 = temp_list[1]
    graph[temp_num1].append(temp_num2)
    graph[temp_num1].sort()
    graph[temp_num2].append(temp_num1)
    graph[temp_num2].sort()

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

for i in result_dfs:
    if i == result_dfs[len(result_dfs)-1]:
        print(i, end='\n')
    else:
        print(i, end=' ')
for i in result_bfs:
    print(i, end=' ')

DFS와 BFS의 기본 개념을 묻는 문제였다.

 

필자는 나동빈 저자의 '이것이 코딩테스트다' 라는 책을 통해 파이썬 알고리즘을 공부하고 있는데, 책에서 소개된 파이썬 예제를 응용하여 해결할 수 있었다.

 

탐색할 그래프는 리스트를 통해 표현했다. 그래프의 1번 인덱스에 해당하는 리스트에는 1번과 연결된 노드번호, 2번 인덱스에 해당하는 리스트에는 2번과 연결된 노드번호, ... 식으로 그래프를 표현했다.

 

처리 조건에서 그래프를 탐색할 때 노드 번호가 작은 순서부터 탐색한다는 조건을 만족시키기 위해 sort()를 사용했다.

왜냐하면 노드번호가 큰 순서부터 입력이 주어질 수 있기 때문이었다.

 

또 마지막에 결과물을 출력할 때, 단순히 print(result_dfs), print(result_bfs)로 결과를 출력했더니 오답이 되었고 이를 출력 예시에 맞게 리스트의 데이터를 순서대로 출력하는 형태로 바꾸었더니 정답으로 인정되었다.

 

처음 코드를 짤 때 DFS, BFS적 사고를 통한 코드 작성이 어려워 책을 많이 참고한 점이 아쉽다.

이런 식의 프로그램 작성은 약간의 응용에도 쉽게 무너질수 있으니 해당 코드를 계속 반추하며 DFS, BFS적 사고에 기반한 코드를 작성할 수 있도록 충분한 연습이 필요해 보인다.

 

※ 해당 게시물은 개인 코딩 공부를 위해 작성하는 글입니다. 문제가 있을 경우 dusrlf2003@naver.com으로 연락주세요!