[BOJ / 백준] 1260번 DFS와 BFS 파이썬(Python) 문제 풀이

문제

 

 

문제 링크 : https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

 

CODE

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

def dfs(edges, v, visited):
    visited[v] = True
    print(v, end=' ')

    for e in edges[v]:
        if not visited[e]:
            dfs(edges, e, visited)


def bfs(edges, v, visited):
    queue = deque([v])
    visited[v] = True

    while queue:
        now = queue.popleft()
        print(now, end=' ')

        for e in edges[now]:
            if not visited[e]:
                queue.append(e)
                visited[e] = True


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

    for i in range(1, n + 1):
        edges[i].sort()

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

 

 

 

 

 

풀이

💡 idea

- 지난 글에 정리했던 DFS, BFS 함수를 거의 그대로 사용했다

[Algorithm] DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) : 파이썬 예제 코드 + 인접 행렬, 인접 리스트

- 정점번호가 작은 것부터 방문하기 위한 정렬이 필요하다

 

 

 

💡 implementation

- 양방향 그래프이기 때문에 두 정점 모두에 간선 추가

    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)

 

- 각 간선 정보에 대해 모두 정렬하기 위해 for문을 사용

    for i in range(1, n + 1):
        edges[i].sort()

 

- 방문한 노드에 대한 flag를 저장한 visited는 dfs에서 사용하고 bfs에서 사용할 때 다시 초기화해서 사용한다

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

 

 

 

 

결과