[백준] 1260 DFS 와 BFS Python

1. 문제

그래프를 DFS 로 탐색한 결과와 BFS 로 탐색한 결과를 출력하는 프로그램을 작성하시오 
정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V 
M 개의 줄에는 간선이 연결하는 두 정점의 번호가 주어지고, 입력으로 주어지는 간선은 양방향이다
1 <= N <= 1000, 1 <= M <= 10,000 

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

2. 알고리즘 분류

* 그래프 이론

* 그래프 탐색

* 너비 우선 탐색

* 깊이 우선 탐색

3. 접근 방식

DFS (Stack 이용) 와 BFS (deque 이용) 를 공부한 김에 관련 문제를 풀어봤다

DFS, BFS 개념 정리

[TIL] DFS 깊이 우선 탐색 BFS 너비 우선 탐색

 

4. 코드 구현

첫번째 시도

from collections import deque

def dfs(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        v = stack.pop()

        if not visited[v]:
            print(v, end=' ')
            visited[v] = True

            for neighbor in reversed(graph[v]):
                if not visited[neighbor]:
                    stack.append(neighbor)

def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])

    while queue:
        v = queue.popleft()

        if not visited[v]:
            print(v, end=' ')
            visited[v] = True

            for neighbor in graph[v]:
                if not visited[neighbor]:
                    queue.append(neighbor)

if __name__ == '__main__':
    n, m, v = list(map(int, input().split()))
    graph = [ [] for _ in range(n+1)]

    for _ in range(m):
        # 입력으로 주어지는 간선은 양방향이다 
        u, w = map(int, input().split())
        graph[u].append(w)
        graph[w].append(u)

    dfs(graph, v)
    print() # 줄바꿈
    bfs(graph, v)
    print() # 줄바꿈

DFS, BFS 잘 썼는데 틀렸다고 한다,.....

두번째 시도

from collections import deque

def dfs(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        v = stack.pop()

        if not visited[v]:
            print(v, end=' ')
            visited[v] = True

            # 이웃 노드를 역순으로 스택에 추가 
            for neighbor in sorted(graph[v], reverse=True):
                if not visited[neighbor]:
                    stack.append(neighbor)

def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])

    while queue:
        v = queue.popleft()

        if not visited[v]:
            print(v, end=' ')
            visited[v] = True

            # 이웃 노드를 정렬하여 큐에 추가
            for neighbor in sorted(graph[v]):
                if not visited[neighbor]:
                    queue.append(neighbor)

if __name__ == '__main__':
    n, m, v = list(map(int, input().split()))
    graph = [ [] for _ in range(n+1)]

    for _ in range(m):
        # 입력으로 주어지는 간선은 양방향이다 
        u, w = map(int, input().split())
        graph[u].append(w)
        graph[w].append(u)

    dfs(graph, v)
    print() # 줄바꿈
    bfs(graph, v)
    print() # 줄바꿈

 

그래프가 정렬되어 있지 않기 때문에 순회 순서가 예상과 다를 수 있다고 피드백을 받아서

이웃 노드 (neighbor) 를 찾을 때 정렬을 추가해줬다 (+ dfs 는 reverse=True 도 해줌)