[Baekjoon]백준 1260 DFS와 BFS(실버 2) - Python

문제설명

예제

문제를 살펴보면 이전에 작성한 코드를 활용하여 DFS와 BFS로 노드를 탐색하고 탐색한 노드들의 번호를 

순서대로 출력하면 된다 이전에는 visited 리스트에 방문 순서를 저장하였기때문에 해당 함수들을 그대로 사용하되,

마지막 출력 형식을 바꾸어주기만 하였다

 

대신 같은 변수를 쓰면 헷갈리기도 하고 값이 초기화가 제대로 되지 않을 수 있기 때문에 visited리스트와 cnt 변수는

각 함수 역할(dfs, bfs)에 맞게 다시 선언해주었다 visited 리스트를 그대로 사용하지 않고 다른 방법을 사용할지

잠깐 고민을 해보았지만 그렇게 되면 dfs, bfs의 가독성이 더 떨어지지 않을까 라는 생각으로 그대로 사용하였다

이후 visited 리스트에 저장된 방문순서를 바탕으로 각 순서에 따라 어떠한 노드를 방문하였는지

새로운 리스트를 만들어 값을 저장해주었고, 이를 바탕으로 예제를 입력하면 예제 3을 제외하고 정확한 출력이 나오게 된다

 

원래 for i in range(1, vertex+1)을 사용하여 print(Answer_bfs[i], end=' ')와 같은 방식으로 사용하였는데 

이렇게 하였더니 마지막 예제에서 0이 너무 많이 출력되는 것을 확인하였다 그래서 if문을 추가하여 값이 유효할때

print()를 하도록 하였고, 이를 통해 정답임을 확인할 수 있었다

import sys
input = sys.stdin.readline
from collections import deque

def bfs(start):
    global cnt_bfs
    queue = deque([start])
    visited_bfs[start] = cnt_bfs

    while queue:
        cur = queue.popleft()
        for neighbor in graph[cur]:
            if visited_bfs[neighbor] == 0:
                cnt_bfs += 1
                visited_bfs[neighbor] = cnt_bfs
                queue.append(neighbor)

def dfs(idx):
    global cnt_dfs
    visited_dfs[idx] = cnt_dfs
    graph[idx].sort()
    for i in graph[idx]:
        if visited_dfs[i] == 0:
            cnt_dfs += 1
            dfs(i)

vertex, edge, starting = map(int, input().split())
graph = [[] for _ in range(vertex+1)]
visited_bfs = [0] * (vertex+1)
visited_dfs = [0] * (vertex+1)
cnt_bfs = 1
cnt_dfs = 1

for _ in range(edge):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
for g in graph:
    g.sort()

dfs(starting)    
bfs(starting)

Answer_dfs = [0] * (vertex+1)
Answer_bfs = [0] * (vertex+1)
for i in range(1, vertex+1):
    Answer_dfs[visited_dfs[i]] = i
for i in range(1, vertex+1):
    Answer_bfs[visited_bfs[i]] = i
    
for i in range(1, vertex+1):
    if Answer_dfs[i]:
        print(Answer_dfs[i], end=' ')
print()
for i in range(1, vertex+1):
    if Answer_bfs[i]:
        print(Answer_bfs[i], end=' ')