[코테]99클럽 코테스터디 6일차 TIL 백준 1260 DFS와 BFS

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

99클럽 1주차는 이분탐색이나 투포인터 문제를 풀었다면, 2주차의 문제 주제는 그래프 탐색인 것 같다. 이번 문제는 DFS와 BFS의 개념을 확실히 알 수 있는 문제이다. 

먼저 그래프는 두가지 형태로 입력받을 수 있는데, 인접행렬과 인접리스트 형태이다. 

인접행렬과 인접리스트의 차이는 다음과 같다. 

예를 들어 다음과 같은 그래프가 있다고 가정해볼 때, 인접행렬과 인접리스트는 다음과 같이 입력될 수 있다. 

1. 인접행렬 : 각 노드가 연결되어 있는지 아닌지를 0혹은 1로 나타낸 행렬이다. (모든 노드에 대한 연결정보를 저장하므로, 공간메모리가 소모되서 잘 안쓰이는 것 같다.)

2. 인접리스트 : 각 연결 정보를 중첩리스트를 활용하여 나타낸 것이다. 보통 정점의 개수 + 1 만큼 빈 리스트를 주는데, 그 이유는 리스트의 각 인덱스가 정점의 번호 역할을 하기 때문에 0번 역할을 하는 리스트는 비워놓기 때문이다. 

graph = [[],[2,3,4],[1,4],[1,4],[1,2,3]]으로 작성해볼 수 있다. 

 

이제 이문제의 핵심인 DFS와 BFS의 차이점은 한 마디로 노드의 탐색을 깊이를 우선으로 하는지, 너비를 우선으로 하는지이다. 

DFS는 깊이 우선탐색으로, 시작 노드로부터 출발해서 연결되어지는 노드 끝까지 계속해서 탐색한다. 이 특징을 재귀함수로 다음과 같이 표현할 수 있다. 

def dfs(start):

    visited[start] = True

    print(start, end=" ")

    for node in graph[start]:

        if not visited[node]:

            dfs(node)

           

BFS는 너비 우선탐색으로, 시작노드부터 출발해서 양옆의 노드부터 층층이 탐색하는 방식이다. 큐를 이용해서 표현할 수 있다. 

def bfs(start):

    queue = deque()

    queue.append(start)

    visited[start] = True

    while queue:

        node = queue.popleft()

        print(node, end=" ")

        for i in graph[node]:

            if not visited[i]:

                visited[i] = True

                queue.append(i)

dfs와 bfs 구현도 중요하지만, 또 한가지 중요한 점은  방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하게 하기 위하여 입력한 인접리스트를 오름차순으로 정렬해준 다음 dfs와 bfs에 넣어주어야 한다는 것이다. 

전체 코드는 다음과 같다. 

import sys

from collections import deque

read = sys.stdin.readline

N, M, V = map(int, read().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):

    inputs = list(map(int, read().split()))

    graph[inputs[0]].append(inputs[1])

    graph[inputs[1]].append(inputs[0])

for i in graph:

    i.sort()

def dfs(start):

    visited[start] = True

    print(start, end=" ")

    for node in graph[start]:

        if not visited[node]:

            dfs(node)

           

def bfs(start):

    queue = deque()

    queue.append(start)

    visited[start] = True

    while queue:

        node = queue.popleft()

        print(node, end=" ")

        for i in graph[node]:

            if not visited[i]:

                visited[i] = True

                queue.append(i)

visited = [False] * (N+1)

dfs(V)

print()

visited = [False] * (N+1)

bfs(V)