[백준 1260] DFS와 BFS

백준 1260 : DFS와 BFS

문제

N : 정점
M : 간선
V : 정점 번호

연결된 정점을 주고, DFS와 BFS의 결과를 출력하는 문제이다.
반복문을 통해 변수 graph[a].append(b), graph[b].append(a)를 해준다.

예제입력1을 넣어보면 [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]] 이와 같이 출력되는데, 이는 인덱스 번호를 정점의 번호와 같다고 본다. 정점 1과 연결된 수가 2,3,4 정점 2와 연결된 수가 1,4 ... 라는 뜻이다.

graph[i].sort()를 하는 이유는 문제에 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,라는 조건 때문이다.

dfs

그 후 dfs를 진행시켜!
dfs 코드는 굉장히 간단하당.

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

    for i in graph[v]:
        if not visited[i]:
            dfs(i)

dfs
다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘
1. 현재 노드 방문 처리
2. 연결된 노드들 재귀적으로 방문 (방문안된 상태라면 재귀로 방문)

예제입력1을 예시로 해서 생각해보자. 시작 정점이 1이므로 dfs(1)이 진행된다.
visted[1] = True로 방문체크를 해준 후 print(v)로 정답을 출력한다.

그 후 graph[1] (==[2,3,4])를 반복문을 돌며 방문했으면 지나가고, 방문하지 않았으면 dfs(i)를 재귀호출 해준다. 따라서 dfs(2)가 진행된다.

또 반복문을 돌며 graph[2] (==[1,4])를 확인하는데, 1은 맨 처음 방문했으므로 4를 방문해준다. 그래서 dfs(4)가 진행된다.
그 다음은 3을 방문한다!

따라서 dfs 방문 정점 순서는 1 2 4 3이 되는 것이다.

bfs

그다음은 bfs를 해보자.
dfs는 stack을 쓰는 반면 bfs는 queue를 쓴다. 따라서 from collections import deque 를 해주고 deque를 사용한다.

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

    while queue:
        q = queue.popleft()
        print(q, end=' ')
        for i in graph[q]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

bfs
그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 수행할 수 없을 때까지 반복

예제입력1을 예시로 해서 생각해보자. 먼저 deque([1])로 정점을 queue에 집어넣는다. 그리고 visited[1]=True로 방문 처리를 해준다. 그 후 while queue로 큐가 빌 때까지 반복한다.

queue.popleft()를 하여 큐에서 노드를 꺼낸 뒤 (현재 1) print(q)로 결과를 출력해준다. 그럼 맨 처음 결과는 1이 출력된다.

graph[1] (==[2,3,4])을 반복문을 돈다. 방문하지 않았으면, queue에 해당 정점을 추가한다. 2,3,4 모두 방문하지 않은 상태이므로 queue에는 deque([2,3,4])가 들어가게 된다. 그리고 이 2,3,4는 visited[i]=True로 모두 방문처리 된다.

그 다음 q=queue.popleft()로 2가 출력된다. graph[2] (==[1,4])는 이미 모두 방문처리 되었으므로 q = queue.popleft()로 다시 돌아가 3이 출력된다. 마찬가지로 다시 돌아가 4가 출력된다.

따라서 bfs 방문 정점 순서는 1 2 3 4가 되는 것이다.

끝!

전체 코드

from collections import deque


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

    for i in graph[v]:
        if not visited[i]:
            dfs(i)


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

    while queue:
        q = queue.popleft()
        print(q, end=' ')
        for i in graph[q]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, N+1):
    graph[i].sort()

dfs(V)
visited = [False] * (N+1)
print()
bfs(V)