백준 알고리즘 1260 (DFS와 BFS) - python

[문제] 백준 알고리즘 1260 (DFS와 BFS)

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

1260번: DFS와 BFS

 

노드와 간선이 주어지면, DFS와 BFS로 경로를 출력하는 문제이다.

N개의 노드, M개의 간선이고, 노드 V부터 탐색을 시작한다.

 

예제 입력 1을 기준으로 설명하자면,

N, M, V = 4, 5, 1 이면서, 

(1, 2)  (1, 3)  (1, 4)  (2, 4)  (3, 4) 가 차례로 입력(tuple로 표현함)으로 들어왔다.

graph라는 변수에 (1, 2)가 먼저 graph[1].append(2), graph[2].append(1) 의 식으로 채워진다.

(1, 3)에서는 graph[1].append(3), graph[3].append(1) 와 같이 채워지고

     ...                 ....                        .....

(3, 4)에서는 graph[3].append(4), graph[4].append(3) 까지 채워지게 된다.

 

이 때, graph를 출력해보면, [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]] 이 된다.

(맨 처음 0번째의 []은 편의적 용도) index번째 노드에 [연결된 노드들]을 나타낸다.

1번째는 [2, 3, 4] 노드들, 즉, 1과 2, 3, 4가 간선으로 연결되어있다는 뜻이다.

2번째는 [1, 4] 노드들, 즉, 2와 1, 4가 간선으로 연결되어있다는 뜻이 된다.

 

이 때, graph의 내부를 sort() 시킨다. 간선이 양방향 연결이어서 방향이 없기 때문이다.

노드 V에서부터 가야하기 때문에, 위상 정렬을 하기 위해서이다. (선수 과목을 이수!)

 

1. DFS를 풀기 위해서는, Stack과 재귀 함수의 활용이 가장 중요한 부분이다.

노드 V를 시작으로 Stack 해주고, 방문여부를 확인하면서 

V에 연결된 노드의 가장 첫 노드를 graph에서 index로 일단 따라간다. (Depth First)

재귀가 마무리 되면, Stack을 String으로 출력해준다.

 

[Code]

import sys
n, m, v = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    link = tuple(map(int, sys.stdin.readline().split()))
    graph[link[0]].append(link[1])
    graph[link[1]].append(link[0])
for link in graph:
    link.sort()

visited = [False] * (n + 1)
stack = []
def solve_dfs(n, v):
    stack.append(v)
    visited[v] = True
    for next_v in graph[v]:
        if not visited[next_v]:
            solve_dfs(n, next_v)
solve_dfs(n, v)
print(' '.join(map(str, stack)))

 

2. (이어서) BFS를 풀기 위해서는, Queue와 While문의 활용이 가장 중요한 부분이다.

노드 V를 시작으로 Queue에 넣어 주고, 방문여부를 확인하면서 

V에 연결된 노드의 모든 노드를 먼저 Queue에 넣어준다. (Breadth First)

출력용 배열에 V부터, Queue의 0번째를 pop() 시키면서 Queue에 요소가 없을 때까지 진행한다.

 

[Code]

visited = [False] * (n + 1)
queue = []
out = []
def solve_bfs(n, v):
    queue.append(v)
    while queue:
        next_v = queue.pop(0)
        out.append(next_v)
        visited[next_v] = True
        for i in graph[next_v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
solve_bfs(n, v)
print(' '.join(map(str, out)))